Cobra Effect · Maths and proof
Seven bridges and a walk that could not be done
How Euler proved a walk impossible without trying a single route.
7 cards, read aloud in 2:35, with a test and sources.
The city of Konigsberg had seven bridges over its river.
The river Pregel split around an island, and the bridges joined four separate areas of land. People wondered whether a walk could cross every bridge exactly once. Nobody could find such a walk, but nobody could prove it was impossible either.
The puzzle reached Leonhard Euler, a mathematician in St Petersburg.
Euler never walked the bridges himself. He found the question oddly interesting, because neither geometry, nor algebra, nor ordinary counting seemed enough to settle it. In 1735, he presented a paper about it to the St Petersburg Academy of Sciences.
Euler saw that shapes and distances did not matter.
All that counted was which areas of land each bridge connected. Later mathematicians would draw this as dots joined by lines. Euler himself labelled the areas with letters, and reasoned by counting.
Then he counted how many bridges touched each area.
Every time a walker passes through an area, they use one bridge to arrive and another to leave. So an area passed through in the middle of a walk needs an even number of bridges. Only the start and the end of the walk can have an odd number.
In Konigsberg, all four areas had an odd number of bridges.
A walk can have at most two odd areas, one at each end. With four, no walk crossing every bridge exactly once could exist. Euler had proved the walk impossible without trying a single route.
His rule worked for any arrangement of bridges.
If more than two areas have an odd number of bridges, no such walk exists. Euler did not prove the reverse, that a walk always exists when the rule allows it. That proof was published in 1873. His paper is often called the first in graph theory, the mathematics of networks.
So when a puzzle resists every attempt, ask what all the attempts have in common.
Euler did not search harder for a route. He found a feature that every possible route must have, and showed Konigsberg could not supply it. Stepping back from the details can turn a puzzle into a proof.
Sources
- Solutio problematis ad geometriam situs pertinentis, The Euler Archive. Euler’s paper on the bridges, with scans of the original.
- An Historical Note: Euler’s Konigsberg Letters, Journal of Graph Theory, 1988. Euler’s letters about the puzzle, and what he did and did not prove.
- How the Seven Bridges of Konigsberg Spawned New Math, Scientific American. An explainer on the puzzle and its legacy.
Nearby ideas
- The primes never run out. How a proof over two thousand years old shows the primes never run out.
- Some infinities are bigger than others. How Georg Cantor showed that some infinities are larger than others.
- The limits of proof. How Kurt Godel found limits that no system of proof can escape.
- The margin that was too small. How Andrew Wiles proved Fermat's three hundred year old claim.
- The long journey of zero. How zero grew from a gap in a number into a number in its own right.