The Seven Bridges of Königsberg
How a simple puzzle laid the foundations for a whole new area of mathematics
One of Leonhard Euler’s best known contributions to mathematics was to tackle and solve the Königsberg Bridges puzzle.
​
Königsberg was a city in Prussia, a German state which no longer exists but which was important in the eighteenth century. Now called Kaliningrad, the city is situated in Russia, near to Poland and Lithuania.
​
The picturesque city had a river running through its heart and in 1730 there were seven bridges linking parts of the city as shown in the map.
The ‘ö’ symbol is called an umlaut and changes the ‘o’ sound to something sounding like the ‘err’ in ‘worm’.
In the evenings and at weekends, many of the residents of Königsberg would take a walk around the city admiring its charming buildings, waterways and parks. They would cross the bridges several times as they walked.
Some residents started to think about a question.
​
"Is it possible to walk around the city, crossing every bridge exactly once?"
​
Many people tried but none could succeed. Why was this?
​
Surely there must be a way...
Maybe you will be able to solve the puzzle!
​
A simplified version of the map shows the layout of the bridges and 'islands'. You can use this to attempt the problem yourself.
​
Remember that you need to be able to find a path that crosses every bridge exactly once. You can start and finish anywhere that you choose.
Come back and read the rest of the article when you think you have found a successful route (or maybe when you have given up!)
The problem came to Leonhard Euler’s attention when the Mayor of a nearby city called Danzig (now GdaÅ„sk in Poland) pleaded with Euler to tackle the problem. Euler was not keen as he did not feel it was really a mathematical problem, stating in a letter to the Mayor:
“Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle. Because of this, I do not know why even questions which bear so little relationship to mathematics are solved more quickly by mathematicians than by others.”
In spite of his misgivings, the Königsberg bridges problem played on Euler’s mind and he could not leave it alone for very long.
Having not originally felt that the puzzle was a mathematical problem, Euler came to realise that the problem was indeed mathematical. He began to feel that it could be solved by logical thought and ultimately a rigorous mathematical proof must be possible.
​
If anybody could solve the problem, then surely it must be Leonhard Euler!
​
Indeed, by 1736 Euler had found a solution, and he extended this to any city with any number of islands, rivers and bridges.
The people of Königsberg could finally see why the tour had been so hard to complete.
​
Leonhard Euler’s work on the Königsberg Bridge problem laid the foundations of Graph Theory which in turn led to the development of Topology, another mathematical subject of immense importance.
​
Toplogy studies how objects retain certain features under transformations which bend and stretch the object but do not cut or tear it.
​
In Topology, a mug and a bagel are considered to be equivalent - because one can be transformed into the other by bending and stretching. Both have one ‘hole’.
​
Of course, to achieve this they must both be made from a flexible and stretchy material.
Both the mug and the bagel are considered to be fundamentally different to a double torus (below) which has two ‘holes’:
Graph Theory & Topology are studied to this day and if you read mathematics at university, it is very likely that you will meet both of these exciting topics.
So how can we find a route around the Königsberg bridges?
​
The unfortunate answer is that we will never find a route that crosses each bridge exactly once and this is what Euler managed to prove. The puzzle is impossible to solve!
​
Euler’s clever idea was to represent the map by a graph drawing. This makes the puzzle easier to analyse. Can you see how the graph drawing below represents the Königsberg puzzle?
Each vertex represents land and each edge represents a bridge.
Euler proved that a route that crosses each bridge exactly once is impossible. He used the following argument:
1. We must travel along each edge once.
​
​
2. We must be able to visit and leave every vertex in order to continue our route.
​
​
3. Because of point 2, each vertex must have an even number of edges meeting there (one to get there and one to leave each time we visit).
​
​
4. Point 2 does not apply to the starting vertex and final vertex as we only need to leave the starting vertex and arrive at the final vertex once.
​
​
5. Therefore, all vertices need to be of even degree except the start and end vertices(which may be even) .
It might take more than one reading of the proof before you accept it as true.
Euler’s proof means that in any graph diagram, a journey that crosses each edge exactly once may not be possible. It will only be possible if the graph drawing has either zero vertices of odd degree or two vertices of odd degree.
​
A solution to the Königsberg bridges puzzle can only exist if the associated graph diagram has zero or two vertices of odd degree.
​
The Königsberg Bridges graph diagram has vertices of degrees 5, 3, 3 and 3. There are four vertices of odd degree, and therefore the puzzle can never be solved.
​
This marked the end of the line for the puzzle which had fascinated so many people for so long. At the same time, the puzzle had given life to the subject of Graph Theory.
Two of Königsberg’s bridges were destroyed in World War 2, meaning that the city’s bridges can now be represented by this diagram.
Today, it is possible to cross each bridge exactly once as the loss of two bridges leaves vertices of degree 2, 2, 3 and 3. Only two of the vertices have odd degree
Check that you can find a route around the modern city which crosses each bridge exactly once and if you ever visit Kaliningrad, maybe take the tour for yourself.
​
It is curious to think that if a European city had been designed slightly differently then whole branches of mathematics may have looked very different today.