The Seven Bridges

  • Hard
  • Geometry and grid puzzles
  • Tests: Proving a walk impossible by counting ends

The puzzle

Konigsberg sat on two banks and two islands, joined by seven bridges. The two islands and the banks had 5, 3, 3 and 3 bridge-ends respectively.

Is there a walk that crosses every bridge exactly once? Prove your answer rather than searching.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Forget the map. All that matters is how many bridge-ends meet at each landmass.

Hint 2

Think about passing THROUGH a landmass: you arrive on one bridge and leave on another, so bridges there get used in pairs.

Show the answer Hide the answer

No such walk exists. All four landmasses have an odd number of bridges, and a walk of this kind allows at most two.

How to get there

Every time the walk passes through a landmass it uses two bridges there, one in and one out. So the bridges at any landmass are used in pairs - except at the place you start and the place you finish, where one bridge is unpaired.

A landmass with an odd number of bridges must therefore be the start or the end. There is one start and one end, so at most two landmasses may have an odd count.

Konigsberg has four odd landmasses - 5, 3, 3 and 3 - which is two too many. No amount of searching will help, because the obstruction is in the counting. Euler published this in 1736 and in doing so invented graph theory: the shapes, distances and positions were all irrelevant, and only the connections mattered.

The technique worth keeping

To prove a route impossible, find a quantity every legal move preserves and show the goal violates it. Counting odd-degree vertices settles every trace-without-lifting puzzle: zero of them means a closed route, exactly two means an open one, and anything else means no route at all.