Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Maths in a minute: The bridges of Königsberg

      20 November, 2013

      In the eighteenth century the city we now know as Kaliningrad was called Königsberg and it was part of Prussia. Like many other great cities Königsberg was divided by a river, called the Pregel. It contained two islands and there were seven bridges linking the various land masses. A famous puzzle at the time was to find a walk through the city that crossed every bridge exactly once. Many people claimed they had found such a walk but when asked to reproduce it no one was able to. In 1736 the mathematician Leonhard Euler explained why: he showed that such a walk didn't exist.

      Euler's solution is surprisingly simple — once you look at the problem in the right way. The trick is to get rid of all unnecessary information. It doesn't matter what path the walk takes on the various land masses. It doesn't matter what shape the land masses are, or what shape the river is, or what shape the bridges are. So you might as well represent each land mass by a dot and a bridge by a line. You don't have to be geographically accurate at all: as long as you don't disturb the connectivity of the dots, which is connected to which, you can distort your picture in any way you like without changing the problem.

      Transforming the problem. Image: Bogdan Giuşcă.

      Once you have represented the problem in this way, its features are much easier to see. After playing around with it for a while you might notice the following: when you arrive at a dot via a line (enter a land mass via the bridge), then unless it is the final dot at which your walk ends, you need to leave it again, by a different line as those are the rules of the game. That is, any dot that is not the starting and end-point of your walk needs to have an even number of lines coming out of it: for every line along which you enter there has to be one to leave.

      For a walk that crosses every line exactly once to be possible, at most two dots can have an odd number of lines coming out of them. In fact there have to be either two odd dots or none at all. In the former case the two correspond to the starting and end points of the walk and in the latter, the starting and end points are the same. In the Königsberg problem, however, all dots have an odd number of lines coming out of them, so a walk that crosses every bridge is impossible.

      Euler's result marked the beginning of graph theory, the study of networks made of dots connected by lines. He was also able to show that if a graph satisfies the condition above, that the number of dots with an odd number of lines is either zero or two, then there will always be a path through it that crosses every line exactly once.

      The result also marked the beginning of topology, which studies shapes only in terms of their connectivity, without taking note of distances and angles. The London tube map is a great example of the topological triumph. By distorting distances and angles it turns what would otherwise be an unintelligible mess into a map that every tourist can read effortlessly. You can find out more here.


      About this article

      This article was inspired by content on our sister site Wild Maths, which encourages students to explore maths beyond the classroom and designed to nurture mathematical creativity. The site is aimed at 7 to 16 year-olds, but open to all. It provides games, investigations, stories and spaces to explore, where discoveries are to be made. Some have starting points, some a big question and others offer you a free space to investigate.

      Read more about...
      Bridges of Konigsberg
      graph theory
      topology
      creativity
      Maths in a minute
      • Log in or register to post comments

      math.nights

      14 March 2016

      Permalink

      To Arabic: https://goo.gl/HIGvPM

      • Log in or register to post comments

      Read more about...

      Bridges of Konigsberg
      graph theory
      topology
      creativity
      Maths in a minute
      University of Cambridge logo

      Plus is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms