Seven bridges, no route

A city on a river had seven bridges, and its people asked whether one walk could cross each of them exactly once and end where it began. It cannot, and the reason fits in one count per piece of land.

A walk through Königsberg

Königsberg — modern Kaliningrad, in Russia — is cut up by waterways. In the 1700s seven bridges crossed them, joining four separate pieces of land. Could you cross every bridge exactly once and come home? That was the Königsberg bridge problem.

Leonhard Euler settled it in 1735. He did it by throwing the map away.

Why the answer matters more than the walk

Nobody needed the stroll; what mattered was Euler's move. The shape of the river and the size of each island make no difference. Only one thing does: which land connects to which, by how many bridges.

That move is the start of graph theory. A graph is a set of points, called vertices, and lines joining them, called edges. It is the same question a delivery route asks today: can a truck cover every street once without doubling back?

One count decides it

Euler drew one vertex for each land mass and one edge for each bridge. Two edges may join the same pair of vertices, because two bridges can join the same two shores. The walk becomes a graph question: is there a circuit — a walk that uses every edge exactly once and returns to its start?

The degree of a vertex is the number of edges that end there. Here it is the number of bridges touching a piece of land.

Watch any vertex the walk passes through. It arrives along one edge and leaves along another, so every visit uses two edges. If the walk must come home, the start works the same way: the first step out pairs with the last step in. So on a circuit every vertex has its edges used in pairs, and its degree must be even.

Take a vertex of degree 3. You arrive and leave, using two edges. Later the third brings you in again, and there is no unused way out: you are stranded, or you cross a bridge twice.

Four odd numbers

On the map drawn above, which is our own schematic of the seven bridges, the island has five bridges and the other three pieces of land have three each. That count is this page's reading of its own map; the source's text does not spell it out. All four are odd, so there is no circuit.

The rule also runs the other way. A connected graph — one where every vertex can be reached from every other — has an Euler circuit exactly when every vertex has even degree. In the textbook's words, being Eulerian is the same as having vertices with all even degrees.

If you do not have to come home

Drop the demand to return, and you want a trail: every edge once, ending anywhere. Now two vertices are allowed to be odd — the one you leave for good and the one you arrive at and never leave. So an open trail needs exactly two odd vertices — no more — and they are its two ends. Königsberg has four, so it fails even this. No route crosses each bridge exactly once, open or closed.

Double up an existing bridge between two odd pieces of land and both turn even; a trail appears between the two still odd. Doubling a second can make every count even. This is eulerization: duplicating existing edges until every vertex is even, so a circuit exists. Each added edge fixes at most two odd vertices, so the fewest you need is at least half the number of odd ones — two, for Königsberg. In the one-extra-bridge case, Fleury's algorithm finds the actual trail: start at one of the two odd vertices and never cross an edge that would cut the remaining graph in two, unless nothing else is left. (The figure above numbers its route a different way, splicing loops together as it goes; either way the route it shows uses every bridge once.)

In short

Turn the land into vertices and the bridges into edges. A walk uses the edges at each vertex in pairs, in and out, so a circuit needs every degree even and a trail needs exactly two odd. Seven bridges gave four odd counts, and no walk at all.