Can You Cross Every Bridge Just Once?

Many children know a puzzle like the bridges: draw a figure without lifting your pen and without going over any line twice. Lines may cross each other, but you may only turn a corner at a dot.

In Germany children draw a little house this way while chanting Das ist das Haus vom Ni-ko-laus, “This is the house of Nicholas”, one syllable for each of its eight lines. Try it below, then try the other five figures.

Sort the six figures into two groups.

• a.Which figures could you draw? For each one, did you have to start at a particular dot, or did any dot work?
• b.Which figures could you never finish, however you started? How many lines did you manage at most?
• c.Try the house again, starting from one of its top corners, then from the roof. What happens?

What do the special dots have in common? Turn on Count the lines above: it writes beside each dot how many lines meet there.

For the bridges puzzle only one thing matters: which pieces of land each bridge joins. The sizes of the island and the river, the lengths of the bridges: none of it changes which walks are possible. So we can shrink each piece of land to a dot and draw each bridge as a line between two dots.

A drawing of dots joined by lines is called a graph or a network. The dots are its vertices (one is a vertex) and the lines are its edges. You met these words for solids in Grade 7: a cube has 8 vertices and 12 edges.

The number of edges that meet at a vertex is its degree. A vertex is odd if its degree is odd, and even if its degree is even.

In Figure 24.2, Kneiphof (A) has 5 bridges, and the north bank (B), the south bank (C) and Lomse (D) have 3 each. All four vertices of Königsberg are odd.

The pen puzzles are networks too, so the bridges and the drawings are the same puzzle. A walk through a network that uses every edge exactly once is called an Euler path (or Euler trail), after the mathematician who solved Königsberg. When it ends where it began, it is an Euler circuit.

Pick a vertex that is not where the walk starts or ends: one you only pass through. Every time you arrive there by one edge, you leave by another. So each visit uses up two of its edges, one in and one out.

If the walk uses every edge exactly once, such a vertex has all its edges used in pairs, so its degree must be even: 2 if you pass once, 4 if you pass twice, and so on.

The two ends are different. At the start, the first edge is an “out” with no “in” before it; at the finish, the last is an “in” with no “out” after it. So the start and the finish can be odd. If they are the same vertex, its first “out” and last “in” make one more pair, and it is even too.

So a walk that uses every edge exactly once can have at most two odd vertices, and they must be where it starts and where it ends. Königsberg has four odd vertices. Whichever two are the start and the end, the other two would need their bridges in pairs, and 3 bridges can’t be split into pairs. No walk exists. That is the whole proof.

It works the other way round too, and gives a rule for any network:

Euler’s rule. A connected network (one where you can get from any vertex to any other along its edges) has a walk that uses every edge exactly once

• when it has no odd vertices: then you can start anywhere, and you finish where you began (an Euler circuit);
• when it has exactly two odd vertices: then you must start at one of them, and you finish at the other (an Euler path);
• and never when it has more than two odd vertices.

The argument above proves the last line. That the walk really exists in the other two cases took 137 years to prove (see the story below); the next section shows how to find it.

Check it against your six figures:

Figure	Odd vertices	One stroke?
Star	0	yes, from any dot, back to it
Star in a pentagon	0	yes, from any dot, back to it
House	2 (the bottom corners, 3 each)	yes, from one bottom corner to the other
Two panes	2 (the middle of the top and bottom, 3 each)	yes, from one to the other
Crossed square	4 (every corner, 3 each)	no
Three panes	4 (the two middle dots of the top and of the bottom)	no

The handshake fact

Could a network have exactly one odd vertex, a walk with a start but nowhere to end? Try to draw one: you can’t.

Every edge has two ends, so the degrees of all the vertices added together are twice the number of edges, an even number. For Königsberg, 5 + 3 + 3 + 3 = 14 = 2 × 7; for the house, 3 + 3 + 4 + 4 + 2 = 16 = 2 × 8. From this it follows (question e shows how) that every network has an even number of odd vertices: 0, 2, 4, … never 1 or 3. It is called the handshake fact: at any party, the number of guests who shook an odd number of hands is even. Euler proved it in his paper on the bridges.

Euler’s rule tells you whether a walk exists. When it does, how do you find it without trial and error?

1. Count the degrees. If there are two odd vertices, start at one of them. If there are none, start anywhere.
2. Draw one edge at a time, from where you are.
3. Don’t burn your bridges. If you have a choice, never take an edge that would cut you off from edges you haven’t drawn yet. Take it only when it is the last edge left at your vertex.

Breaking rule 3 is how you get stuck halfway: you cross into one part of the network and can’t get back to the edges left behind.

Euler’s rule also shows how to change a network so a walk exists. A new bridge adds 1 to the degree at both its ends: it turns two vertices from odd to even, or even to odd.

In 1905 Königsberg built an eighth bridge, the Kaiserbrücke (Emperor’s Bridge), from the south bank to Lomse. Count again with it (leaving out the railway bridge built downstream in the 1880s): the south bank and Lomse now have 4 bridges each, so only Kneiphof (5) and the north bank (3) are odd.

Then war changed the puzzle. The city was bombed in 1944 and taken by the Soviet army in 1945; it is now Kaliningrad, in Russia. Two bridges onto Kneiphof were destroyed and never rebuilt. The two westernmost were later replaced by one long road bridge that crosses the island from bank to bank, with a way down onto it. The Honey Bridge between the islands and the Wooden Bridge are still the bridges of Euler’s time; the High Bridge was rebuilt in the 1930s.

• Can Three Houses Reach Three Wells Without Paths Crossing? Networks again, but now the question is whether they can be drawn on paper with no lines crossing.
• What Is the Quickest Way Across the Map? Networks with a time on every road, and how to find the fastest route without trying them all.
• Why Do Solids Always Obey One Rule? Count the corners, edges and faces of a solid, from Grade 7: another of Euler’s discoveries.
• Can Four Colors Paint Any Map of Nepal? (Computing, Going Further 6–8) A map as a network of neighbors.
• How Many Ways Round Bhaktapur’s Temples? (Computing, Going Further 6–8) A walk that visits every place once, a puzzle that sounds like Euler’s but is far harder.
• Can a Robot Get Out of Any Maze? (Computing, Going Further 6–8) A maze is a network too.