Seven Bridges of Königsberg

Its negative resolution by Leonhard Euler, in 1736,[1] laid the foundations of graph theory and prefigured the idea of topology.

The difficulty he faced was the development of a suitable technique of analysis, and of subsequent tests that established this assertion with mathematical rigor.

This allowed him to reformulate the problem in abstract terms (laying the foundations of graph theory), eliminating all features except the list of land masses and the bridges connecting them.

In modern language, Euler shows that the possibility of a walk through a graph, traversing each edge exactly once, depends on the degrees of the nodes.

Euler's argument shows that a necessary condition for the walk of the desired form is that the graph be connected and have exactly zero or two nodes of odd degree.

An alternative form of the problem asks for a path that traverses all bridges and also has the same starting and ending point.

Euler's work was presented to the St. Petersburg Academy on 26 August 1735, and published as Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position) in the journal Commentarii academiae scientiarum Petropolitanae in 1741.

Euler's recognition that the key information was the number of bridges and the list of their endpoints (rather than their exact positions) presaged the development of topology.

The difference between the actual layout and the graph schematic is a good example of the idea that topology is not concerned with the rigid shape of objects.

[5] Philosophers have noted that Euler's proof is not about an abstraction or a model of reality, but directly about the real arrangement of bridges.

Rochester Institute of Technology has incorporated the puzzle into the pavement in front of the Gene Polisseni Center, an ice hockey arena that opened in 2014,[11] and the Georgia Institute of Technology also installed a landscape art model of the seven bridges in 2018.

Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges
Modern map of Kaliningrad. Locations of the remaining bridges are highlighted in green, while those destroyed are highlighted in red.
In this picture of the Königsberg Cathedral , the bridge on the right is one of the two surviving bridges from Euler's time.
Comparison of the graphs of the Seven bridges of Konigsberg (top) and Five room puzzle (bottom). The numbers denote the number of edges connected to each node. Nodes with an odd number of edges are shaded orange.