Why can't you cross all seven bridges of Königsberg exactly once?
A puzzle about a city stroll led Leonhard Euler to invent the math behind GPS routes and social networks.
▶ Start the storyBecause every piece of land in Königsberg touched an odd number of bridges, and a walk that crosses each bridge once allows at most two such places: the start and the finish. Leonhard Euler proved this in 1736, and in doing so laid the foundations of graph theory.
The Prussian city, now Kaliningrad in Russia, sat on both banks of the Pregel River around two islands, all linked by seven bridges. The puzzle was simple: could you take a walk that crosses each bridge exactly once?
Euler's genius was to throw away almost everything. The streets, the distances and the shape of the islands don't matter; only which land connects to which, by how many bridges. Shrink each piece of land to a dot and each bridge to a line, and you get what we now call a graph.
Then he counted. Every time you walk onto a piece of land by one bridge, you must leave by another, so any place you pass through needs an even number of bridges. In Königsberg, one landmass had 5 bridges and the other three had 3 each. Four odd places, but only two can be the start and end: the walk is impossible.
5 · 3 · 3 · 3
That dots-and-lines idea now powers GPS route planning and the maps of links behind websites and social media.
Quiz me
0/3
Recap
A walk that crosses every link once needs zero or two places with an odd number of links.
Surprising fact · All four landmasses touched an odd number of bridges (5, 3, 3 and 3), dooming the walk.
Connects to
- 🕸️ What do your friendships, molecules and road maps have in common?
- 🗺️ Why are four colors always enough to color any map?
- Topology
- Eulerian path
- Social network analysis
Sources (2)
No source, no claim. Every fact in this lesson (15 claims) cites at least one of these.