In 1736 a Swiss mathematician was sent a puzzle about a walk through a Prussian city, proved the walk impossible, and accidentally invented an entire branch of mathematics. The city was Königsberg, and it had seven bridges. Could you take a stroll that crossed every one of them exactly once?
Leonhard Euler's answer was no. But the no is the least interesting part. What matters is how he said it: he threw the city away, kept four dots and seven lines, and settled the question with a counting argument you could explain to a ten-year-old.
Throwing away the map
Königsberg straddled the river Pregel, which forked around an island. That left four land masses — the north bank, the south bank, the island of Kneiphof, and a strip of land to the east — joined by seven bridges.
Euler's first move is the one worth stealing. Nothing in the puzzle depends on how long a bridge is, how wide the river runs, or where anything actually sits. Once you are standing on a land mass, you can walk to any bridge that leaves it. So shrink each land mass to a dot and stretch each bridge into a line joining two dots. Geography, distance, shape — all discarded. What survives is pure connection.
That object is what we now call a graph: the dots are vertices, the lines are edges, and the number of edges meeting a vertex is its degree.
Take any land mass that is not where you start and not where you finish. Every time your walk visits it, you arrive across one bridge and leave across a different one. Its bridges are used up in pairs — one in, one out. If the walk uses every bridge exactly once, then every bridge there gets used, so their number must be even.
The start and the finish are the exceptions: you leave the start without having arrived, and arrive at the finish without leaving. Each gets one unpaired bridge.
So the rule is: a walk crossing every edge exactly once — an Euler path — can only exist if at most two vertices have odd degree.
Königsberg's verdict
Count the bridges meeting each land mass: island of Kneiphof: 5. North bank: 3. South bank: 3. East strip: 3.
A quick check: every bridge has two ends, so the degrees must add up to twice the number of bridges. They do — .
Every one of those numbers is odd. Königsberg has four odd vertices, and the rule allows at most two. So the walk does not exist. Not "nobody has found it yet" — it cannot be found, because no amount of cleverness argues with parity.
Notice the asymmetry. To show a walk exists, you exhibit one. To show none exists, you would naively check them all. Euler did neither: he found a property every valid walk must have, and showed Königsberg lacks it. Find the invariant, not the example — that move is most of what mathematicians do all day.
Those "draw this without lifting your pen" puzzles? Count the corners with an odd number of lines: two or fewer and it can be done. Three or more, and no.
Street sweepers and postal rounds want to cover every street once and return to the depot — an Euler circuit, needing zero odd vertices. Where real junctions are odd, planners duplicate the cheapest streets to even them out: the Chinese postman problem. Stranger still, DNA assemblers rebuild a genome from short overlapping fragments by finding an Euler path through a graph whose edges are those fragments [3].
The whole of graph theory grew from these four dots — including the four-colour theorem and six degrees of separation.
The bridges you can walk today
Königsberg's seven bridges cannot be walked, because all four of its land masses have an odd number of bridges and a valid walk permits at most two. A three-line proof — and it cost the world a new field of mathematics.
There is a postscript Euler could not have planned. Two of the seven bridges were destroyed by bombing in 1944 and never rebuilt; two more were later replaced by a modern highway. Five crossings stand in Kaliningrad today, with degrees — only two odd vertices. The rule now says yes: start on the island, finish on the eastern side, and you can cross every bridge in the city exactly once.
One honest caveat. Euler's count shows the condition is necessary — no walk without it. That it is also sufficient Euler asserted but never properly proved; the first full proof came from Carl Hierholzer in 1873 [2]. Even the founding result of a field left homework behind.
References:
[1] Leonhard Euler, "Solutio problematis ad geometriam situs pertinentis," Commentarii academiae scientiarum Petropolitanae 8 (1741), pp. 128–140. (Presented to the St Petersburg Academy in 1736.)
[2] Norman L. Biggs, E. Keith Lloyd and Robin J. Wilson, Graph Theory 1736–1936 (Clarendon Press, Oxford, 1976) — includes translations of both Euler's and Hierholzer's papers.
[3] Pavel A. Pevzner, Haixu Tang and Michael S. Waterman, "An Eulerian path approach to DNA fragment assembly," Proceedings of the National Academy of Sciences 98(17) (2001).
Note: The degree counts above describe the bridges as they stood in Euler's day, and the five crossings of present-day Kaliningrad. The city's bridges have been destroyed, rebuilt and rerouted repeatedly; the mathematics has not moved.