Königsberg, Prussia, 1735. Four landmasses, joined by seven bridges. A question kept getting asked in the city's coffee-houses: could you walk through town crossing each bridge exactly once? No one could do it, but no one could prove it impossible either. The question reached the desk of a 28-year-old Swiss mathematician at the St Petersburg Academy. He answered it, and in answering it invented graph theory.
This page does not ask you to take Euler's proof on faith. It draws the seven bridges, hands you a finger to try the walk with, and lets you watch yourself fail. Then it shows you why, in one line of arithmetic that turns the impossibility into something you can recompute in front of yourself — and lets you point the same one line at the classic schoolbook shapes ("draw this without lifting your pen") to see which are possible and which are not. The proof is exact, the verifier runs in the page, and every figure here is independently reproduced offline in research/what-the-bridges-knew/ (32/32 checks pass).
Praeter illam Geometriae partem, quae circa quantitates versatur, … alterius partis etiamnum admodum ignotae primus mentionem fecit Leibnitzius, quam Geometriam situs vocavit. (Besides that part of geometry that deals with quantities, … Leibniz was the first to mention another part, still quite unknown, which he called the geometry of position.) — Euler 1741, §1, p. 128
The Pregel river ran through Königsberg dividing it into four separable pieces of ground: the north bank (Altstadt), the south bank (Vorstadt), and two islands in midstream — Kneiphof in the middle and Lomse upstream to the east. The seven bridges connected them in a pattern almost any local could draw. Five of the seven touched Kneiphof — making it the busy hub. The other two crossed to Lomse, one from each bank.
It feels like you ought to be able to do it. You almost can. Most attempts get to six of the seven bridges before stranding the last one on the wrong side of an empty crossing. If you press try (auto) the page will exhaust every starting point and every order in which the bridges could be taken — there are 7! ⋅ 4 = 20,160 ordered attempts in total — and report back what it found.
Euler's first move — and the one that founded graph theory — was to throw the map away. The geometry of the river, the lengths of the bridges, the layout of the streets: none of it matters. All that matters is which landmass touches which bridge, and how many bridges meet at each landmass. The town becomes a picture with four dots (one per landmass) and seven lines (one per bridge), and the question becomes one about that picture alone.
The art of letting the answer be small was Euler's, and graph theory is just the discipline of asking the question only of the picture that is left.
| Bridge (Euler's label) | Common name | Joins |
|---|---|---|
| a | Krämerbrücke | Altstadt ↔ Kneiphof |
| b | Schmiedebrücke | Altstadt ↔ Kneiphof |
| c | Grünebrücke | Vorstadt ↔ Kneiphof |
| d | Köttelbrücke | Vorstadt ↔ Kneiphof |
| e | Honigbrücke | Kneiphof ↔ Lomse |
| f | Holzbrücke | Altstadt ↔ Lomse |
| g | Hohe Brücke | Vorstadt ↔ Lomse |
Now consider any landmass in the middle of such a walk — not the start, not the end. Every time you walk into it across a bridge, you must walk out of it across a different bridge. The bridges at this landmass come in matched pairs — one for arriving, one for leaving — so the number of bridges meeting that landmass must be even.
The only landmasses that can dodge this rule are the two endpoints of the walk: at the start you only leave, and at the end you only arrive, each of those costs you one unmatched bridge. So at most two landmasses can have an odd number of bridges. If three or more do, the walk cannot exist.
Königsberg's bridge counts are 5, 3, 3, 3. Four of them odd. No walk.
The same one-line theorem decides every shape in the classic schoolbook puzzle, draw this in one stroke without lifting your pen. The house (square, roof, one diagonal) has two odd vertices — drawable, starting at one corner of the diagonal and ending at the other. K₄ — the square with both diagonals — has four. Not drawable. K₅, where everyone is joined to everyone, has all even degrees — drawable as a closed loop. The proof Euler wrote in 1736 still arbitrates the playground.
One detail is worth pausing on. If you add up the degrees of every vertex — the bridge-counts of every landmass — you count every bridge twice (once for each end). The sum of the degrees is always twice the number of bridges: an even number, no matter what graph you draw. So the number of odd-degree vertices is itself always even. This is the handshake lemma — at a party, the number of people who have shaken an odd number of hands is even — and it is why Euler's "0 or 2" odd vertices is not a coincidence. 1 is impossible. 3 is impossible. The next case after zero is two; the next after two is four.
Königsberg has changed. The Schmiedebrücke and the Köttelbrücke — both joining Kneiphof — fell to RAF bombing on 29–30 August 1944 and were never replaced. The Krämerbrücke and the Grüne Brücke survived the war but were demolished in the early 1970s when a concrete overpass (the Estakada) was driven through the same crossings. Three of the seven still stand at their old sites: the Honigbrücke, the Holzbrücke, and the Hohe Brücke (the last rebuilt 1938). Counting the five connections that remain at Euler's seven sites — three surviving bridges plus two flyover crossings at the Krämer and Grüne positions — the modern degree sequence is 2, 2, 3, 3: two odd vertices, the others even. The walk Euler proved impossible became possible — not as a circuit, but as a trail, beginning at one island and ending at the other. In Instrument II, the +1 bridge preset shows the principle in its simplest form: adding a single connection of the right parity flips the verdict from no to yes. The arithmetic the proof depends on is the same arithmetic that decides whether your morning route through any city — or any subway map, any maze, any network — can be done without doubling back.
Every figure on this page is recomputed by the script below, live, the moment the page loads. It is the same arithmetic the offline file in research/what-the-bridges-knew/ runs and asserts (32/32 checks pass there, including a brute-force search through 20,160 ordered attempts on Königsberg confirming what Euler's three-line argument decides in one).
(running…)
Euler called this geometriam situs — the geometry of position — and the new field he had cracked open behind his single problem. The phrase did not catch; we now call it topology upstream and graph theory downstream, and the bridges are remembered as the founding stone of both. The 28-year-old who walked into the St Petersburg Academy with a small piece of arithmetic about a Prussian town walked out having defined a whole new kind of mathematics — the kind that asks of an object only what cannot be straightened out of it.
Permutation cycles as a survival strategy — the same insight (a graph's structure decides what walks exist on it) for prisoners and boxes. /strata/the-loop-that-saves-them/
Hamiltonian cycles on the permutation graph — a walk that uses every vertex once, where Euler's walks every edge. The harder problem under the campanile. /strata/plain-changes/
Another portal where a few small graphs decide a deep question. Nontransitivity instead of traversal, but the same lesson — the diagram is the proof. /strata/any-loop-you-can-draw/
A page that recomputes its own claim in front of you. There a sentence counts its own letters; here Euler's parity test is run live on every graph you click, including a brute-force confirmation on Königsberg.