The Seven Bridges of Königsberg: Four Odd Vertices Mean No Walk Crosses All Seven Once

The puzzle, stated exactly

Königsberg was the capital of East Prussia, built where the river Pregel splits and rejoins. Four pieces of land faced each other across the water: the Altstadt on the north bank, the Vorstadt on the south bank, the island of Kneiphof in midstream — which carried the cathedral, and later Kant's grave — and Lomse, the strip lying east of the island between the two arms. Seven bridges tied them together, and each one has a name and a date:

• Krämerbrücke (Merchants' Bridge, 1286) — Altstadt to Kneiphof
• Grüne Brücke (Green Bridge, 1322) — Vorstadt to Kneiphof
• Köttelbrücke (Guts Bridge, 1377) — Vorstadt to Kneiphof
• Schmiedebrücke (Blacksmiths' Bridge, 1397) — Altstadt to Kneiphof
• Holzbrücke (Wooden Bridge, 1404) — Altstadt to Lomse
• Hohe Brücke (High Bridge, 1506) — Vorstadt to Lomse
• Honigbrücke (Honey Bridge, 1542) — Kneiphof to Lomse

The Sunday question the townspeople argued over was whether you could take a walk that crossed every bridge exactly once. No boats, no swimming, no crossing half a bridge and turning back, and you may start and finish wherever you like. Nobody found a route, and nobody could say why not — which is a very different thing from a route not existing.

Count the bridges meeting each land mass. Kneiphof touches five (Krämer, Schmiede, Grüne, Köttel, Honig). The Altstadt touches three, the Vorstadt three, Lomse three. Those four numbers, 5, 3, 3, 3, are the entire problem. They also pass the first sanity check: they add to 14, which is exactly twice the number of bridges, because every bridge is counted once at each end.

Why the shape of the map does not matter

Euler's move was to notice that nothing about the route depends on distance, direction, or the shape of the shoreline. Stretch the island, bend the river, move a bridge fifty metres upstream: the set of possible walks is untouched. What survives is a list of four objects and seven links between them. Shrink each land mass to a dot and each bridge to a line and you have what we now call a multigraph — "multi" because two dots can be joined by more than one line, as Kneiphof and the Altstadt are.

The number of line-ends at a dot is its degree. Königsberg's degree sequence is (5, 3, 3, 3). Once the picture is reduced to that, nothing else about Prussia is relevant.

Euler was explicit that this was a new kind of geometry. He opens the paper by invoking Leibniz's geometria situs — geometry of position, as opposed to geometry of magnitude — and says the branch "is concerned only with the determination of position and its properties; it does not involve measurements, nor calculations made with them". That sentence is the seed of topology as well as of graph theory.

One historical correction is worth making, because almost every retelling gets it wrong: Euler did not draw a graph. The dots-and-lines diagram everyone associates with this problem is a later convention. His Figure 1 is a sketch of the actual city, with the land masses labelled A, B, C, D and the bridges labelled a to g, and his argument is carried out on sequences of letters, not on a diagram. The graph drawing is the right way to think about it; it just is not Euler's.

The parity argument, in full

Here is the modern proof of the half that matters — that no such walk can exist. It is three lines long and completely rigorous.

Suppose a walk crosses every bridge exactly once. Fix a land mass v and look at the walk's visits to it. Each time the walk passes through v it arrives on one bridge and departs on another, consuming exactly two of v's bridge-ends. Nothing else can consume a bridge-end at v, because no bridge is used twice.

• If v is neither the start nor the finish, every visit is a pass-through, so deg(v) = 2 × (number of visits) — an even number.
• If v is the start (and not the finish), the opening departure uses one end on its own and every later visit uses two, so deg(v) is odd.
• Symmetrically, if v is the finish, deg(v) is odd.

So at most two land masses may have odd degree, and if exactly two do, they are forced to be the start and the finish. Königsberg has four. Four is more than two. There is no walk. The argument never mentions where the bridges are, so no amount of rebuilding the town in a different shape would help.

Two consequences fall out for free. First, the handshake lemma: summing degrees counts each edge twice, so Σ deg(v) = 2|E| and the number of odd-degree vertices is always even. That is why you will never meet a graph with exactly three odd vertices, and why "four odd" rather than "three odd" is the right description of Königsberg. Second, the condition is about the parity of the degrees and nothing else: a land mass with 101 bridges is no obstacle at all, as long as it is not the third odd one.

Euler's own argument, with his numbers

Euler reached the same conclusion by counting letters, and his version deserves to be shown because it is short and completely concrete.

Describe a route by the sequence of land masses it visits. A route that crosses k bridges visits k + 1 land masses in order, so it is written with k + 1 letters. For Königsberg, k = 7, so any complete route is an 8-letter word.

Now ask how often a given letter must appear. Euler's rule (§14 of the paper): if a land mass X carries an odd number k of bridges, then X must appear in the sequence exactly (k + 1)/2 times — each appearance uses up two of X's bridges except one appearance which uses up one.

Land mass	Bridges	Times it must appear
Kneiphof (A)	5	(5 + 1)/2 = 3
Altstadt (B)	3	(3 + 1)/2 = 2
Vorstadt (C)	3	2
Lomse (D)	3	2
Total letters required		9

Nine letters are required and only eight are available. 9 > 8, so the route does not exist. It is the same parity fact wearing different clothes, and it is entirely arithmetic — which is exactly what Euler found charming about it. Writing to the Viennese court astronomer Giovanni Marinoni on 13 March 1736, he called the question "so banal" yet worth attention precisely because "neither geometry, nor algebra, nor even the art of counting was sufficient to solve it".

What the failed walks prove, and what they do not

The animation on this page tries two routes and watches each one die. Starting on the island you can reach six bridges before you are stranded on the south bank with the Holzbrücke still uncrossed; starting on Lomse you reach six and are stranded on the north bank with the Köttelbrücke uncrossed. Six is genuinely the ceiling: no route does better, and the near-misses are why the townspeople were convinced the answer was "almost".

Those demonstrations are an illustration, not a proof. Two failures rule out two routes. There are 7! = 5,040 orders in which the seven bridges could be attempted, and checking them one at a time is exactly the drudgery Euler wanted to avoid — he says as much, noting that the method of exhaustion "would be too difficult and laborious" and useless for larger towns. The parity count in the previous two sections is the proof; the failed walks show you what the proof is talking about.

There is a second gap that most retellings skip. Euler proved the necessity of the even-degree condition rigorously. He asserted the converse — that whenever the condition holds a route really does exist — without proving it. The first published proof of sufficiency is Carl Hierholzer's, and it arrived 137 years later under sad circumstances: Hierholzer described the argument to colleagues and died in 1871 aged 31, and the paper was reconstructed from their memory and printed in Mathematische Annalen in 1873. His idea is also the standard algorithm today — walk until you get stuck, which on an even-degree graph can only happen back at the start, then splice in cycles built from the edges you missed. It runs in time linear in the number of edges. Fleury's algorithm (1883) is the other classic: never cross a bridge of the graph — an edge whose removal disconnects it — unless you have no other choice.

Fixing Königsberg: one new bridge, or the postman's compromise

Because the obstruction is just "four odd vertices", the repair is arithmetic too. Every new bridge raises two degrees by one each, flipping both parities. So a single new bridge joining the north bank to the south bank turns 3 and 3 into 4 and 4, leaving Kneiphof (5) and Lomse (3) as the only odd land masses. Exactly two odd vertices is precisely the Eulerian-path condition, and a route now exists — forced to start at one of them and finish at the other. Here is one, over all eight bridges:

Kneiphof → Altstadt → Vorstadt (over the new bridge) → Kneiphof → Altstadt → Lomse → Kneiphof → Vorstadt → Lomse

Nine land masses in the sequence, eight bridges, each crossed once. To get a round trip instead you need two new bridges, pairing off all four odd land masses.

If you may not build anything, the honest question becomes the route inspection or Chinese postman problem, posed by Mei-Ko Kwan in 1962: cover every bridge at least once, as cheaply as possible. The recipe is to duplicate a cheapest pairing of the odd vertices, and with all seven bridges the same length the numbers are exact:

• Shortest closed route: 9 crossings. Pair (Kneiphof, Altstadt) via the Krämerbrücke and (Vorstadt, Lomse) via the Hohe Brücke — two repeats on top of the seven.
• Shortest open route: 8 crossings. With free endpoints you only have to fix two of the four odd land masses; repeating the Honigbrücke alone leaves the Altstadt and Vorstadt odd, and the walk runs from one to the other.

And the real city has quietly solved it. Königsberg became Kaliningrad in 1946; the Krämer- and Schmiedebrücke were destroyed in the bombing and siege of 1944–45 and never rebuilt, and the Grüne and Köttel crossings were absorbed into the Estakadny (Overpass) Bridge of 1972, a highway that flies over Kneiphof without stopping on it. Counting the crossings of the two arms in the historic centre on that reading, the degrees are now 1 at Kneiphof, 2 at the Altstadt, 2 at the Vorstadt and 3 at Lomse — exactly two odd. The walk Euler proved impossible is, today, possible, provided you begin on the island and end on Lomse.

What Euler started

The 1736 paper is conventionally called the first paper in graph theory, and unusually for such claims it holds up: it defines a problem in terms of connection alone, proves an impossibility from a counting invariant, and states a general criterion for all towns rather than just this one.

The vocabulary took a while. The word graph in this sense is J. J. Sylvester's, from an 1878 note in Nature drawing an analogy with chemists' structural diagrams. The first textbook is Dénes Kőnig's Theorie der endlichen und unendlichen Graphen (1936) — two centuries after Euler, and a name that merely rhymes with Königsberg.

The sharpest thing the problem teaches is that superficially twinned questions can sit on opposite sides of a computational cliff. "Visit every edge once" is decided by glancing at the parity of the degrees, in time linear in the size of the graph. "Visit every vertex once" — the Hamiltonian problem — has no such test and was proved NP-complete by Richard Karp in 1972. Same graph, same phrasing, wildly different difficulty.

The directed version is the workhorse. A digraph has an Eulerian circuit when it is connected and every vertex has in-degree equal to out-degree, and that fact underwrites de Bruijn sequences and the de Bruijn graph assemblers used in genome sequencing, where reconstructing a chromosome from short reads is posed as finding an Eulerian path — the framing Pevzner, Tang and Waterman set out in 2001. Counting the Eulerian circuits of a digraph even has a closed form, the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte: the number is the count of arborescences times the product of (out-degree(v) − 1)! over all vertices. Counting them in an undirected graph, by contrast, is #P-complete — proved by Brightwell and Winkler in 2005. Deciding whether one exists is trivial; counting how many there are is not.

Five questions you can ask about the same seven bridges, and what each one costs to answer

Question	Exact condition	Cost to decide	Königsberg's answer
Eulerian circuit — every bridge once, finishing where you started	graph connected and every vertex of even degree	linear in the number of edges (Hierholzer, 1873)	No. Degrees are 5, 3, 3, 3 — four of them odd
Eulerian path — every bridge once, start and finish anywhere	graph connected and exactly 0 or 2 vertices of odd degree	linear in the number of edges	No. Four odd vertices, and a walk has only two ends
Hamiltonian path — every land mass once, bridges may be skipped	no usable characterisation; the decision problem is NP-complete (Karp, 1972)	exponential in the worst case	Yes, easily: north bank → island → south bank → east side
Chinese postman — every bridge at least once, shortest closed route	duplicate a minimum-weight pairing of the odd vertices	polynomial (Edmonds–Johnson, 1973)	Yes, in 9 crossings: 7 bridges plus 2 repeated
Eulerian path after building new bridges	add bridges until at most 2 vertices stay odd	linear, once you know the degree sequence	1 new bridge is enough for a path; 2 for a circuit