Worked solution: Euler's degree argument (1736)
Picture squashing each landmass down to a single dot and straightening every winding bridge into a plain line joining two dots — the actual shape of the river banks and islands stops mattering, only which dots each line connects. A stroll that crosses every bridge exactly once becomes a walk along these lines that uses every line exactly once.
Mathematicians now call this kind of walk an Eulerian trail, named after the man who first realised that redrawing the picture this way was the key to the puzzle.
Euler replaces each landmass by a vertex and each bridge by an edge joining the two landmasses it connects, turning the map into a graph with vertices and edges. A walk that crosses every bridge exactly once becomes a walk in that uses every edge exactly once — what is now called an Eulerian trail.
The city of Königsberg (now Kaliningrad, on the Pregel river) consisted of two islands and two riverbanks joined by seven bridges. Its residents debated whether a walk could cross every bridge exactly once; Leonhard Euler heard of the puzzle, and in a short paper read to the St. Petersburg Academy in 1736 he observed that the precise shape of the streets and bridges was irrelevant — only the pattern of which landmasses each bridge joins matters for the question (Biggs, Lloyd & Wilson 1976, Ch. 1).
This translation from geography to a graph is the essential first move: every later step works with the abstract dots-and-lines picture, and the argument that follows will apply to any set of bridges laid out this way, not just Königsberg's.
- Graph, vertex, edge
- A graph is a collection of vertices (dots) together with edges (lines) joining pairs of vertices; here each vertex stands for a landmass and each edge for a bridge.
- Eulerian trail
- A walk through a graph that uses every edge of the graph exactly once (vertices may be revisited, but no edge is crossed twice).