Department of Mathematics, NUI Maynooth: The Bridges of Konigsburg

Königsburg Bridges

Königsburg was renamed Kaliningrad when it and the surrounding territory became part of Russia after the Second World War (look for the small piece of Russia on the Baltic Sea wedged between Lithuania and Northeastern Poland). The city was founded by the Teutonic Knights in the thirteenth century and is the birthplace of Immanuel Kant.

To mathematicians, though, Königsburg is best known because of a puzzle associated with its seven bridges, which were located roughly as illustrated on the right. Its citizens pondered for a long time whether it was possible to walk about the city in such a way that you cross all seven bridges (yellow in diagram) exactly once.

In a 1736 paper which arguably began the field of topology, the great Swiss mathematician Leonhard Euler (1707-1783) proved that this was impossible. In fact Euler gives a criterion which allows one to quickly determine whether there is a solution for any similar problem with any number of bridges connecting any number of landmasses!

Euler first noted that the problem is not changed if we replace the landmasses by vertices (red dots in the diagram) and the bridges by arcs connecting the vertices. We call the resulting assemblage of points and arcs a graph and define the degree of a vertex to be the number of arcs that lead to/from it. Euler proved:

Theorem There exists a (at least one) path on a graph which travels along each arc exactly once if and only if the graph is connected and has none or two points of odd degree.

Such a path on a graph, if it exists, is now called an Euler path in his honour. The K÷nigsburg example has three vertices of degree three and one of degree five, so it has no Euler path and the original puzzle has no solution.

The key to the proof of (one direction of) Euler's result is the realisation that if a vertex is not the initial or final vertex of a path and each bridge is only used once, then the number of arcs that are traversed leading to/from that vertex must be even (each time you go through a vertex, you use one arc to get there and another to leave). This also shows that if there are two vertices of odd degree, one must be the initial vertex of the Euler path and the other the final vertex. Incidentally, notice that the number of vertices of odd degree in any graph must be even since the sum of all the degrees is double the number of vertices.

Exercise: Have a look at the four graphs below and for each of them decide if an Euler graph exists and, if it does exists, find one.

This page was originally designed by Webmaster@maths.may.ie. The statement of the theorem was slightly modified April 8, 2002. .