Königsberg had seven bridges connecting two islands in the river at the center of the city. The puzzle residents passed around was whether a route existed that crossed every bridge exactly once, with no turning back once you had started a crossing. Euler took it up in 1736.
That one, and he proved it. Euler reduced the city to a network in which each landmass is a and each bridge an edge. Such a route needs every node to have an , or exactly two nodes with an odd number, and Königsberg had four odd nodes, so no route could satisfy it.
Graph theory is a nearly 300-year-old field, and it begins with Leonhard Euler. In 1736, working at the Imperial Russian Academy of Sciences, he took up the famous problem of the seven bridges of Königsberg.
The problem itself is simple to state. Seven bridges connected two large islands sitting in the middle of the river at the center of the city. The question was whether a route existed that crossed every bridge once and only once, with each crossing committing you to the far side.
Euler’s move was to throw the city away. He distilled the picture into a in which each node represents a distinct landmass, an island or a river bank, and the edges represent the bridges that connect them.
From there the argument is short. A node you merely pass through needs as many ways in as out, so it must have an even number of edges. A node with an odd number must be the start or the end, and cannot be both. Four of Königsberg’s nodes are odd, so no exists there.
wat. Four landmasses with an odd number of bridges, and the walk dies there.
wat wat
What made the proof matter was not the answer but the move: the positions of the nodes stopped mattering, and only the connections did.
How do we know?
A Cornell networks course traces the argument from the original problem to the modern statement, as the founding example of graph theory.
What is still unknown
A teaching account of a 300-year-old result rather than the original 1736 memoir.
Learn something?
Where to next
Why is there always one point in the coffee that did not move?topology
How many colors does it take to color any map?graph theory
What do you get if you cut a one-sided surface down the middle?topology