A puzzle about a walk
The Prussian city of Königsberg, now Kaliningrad in Russia, was built where the river Pregel splits around an island called the Kneiphof and then flows on as one. In the early eighteenth century seven bridges joined the island, the two river banks and the land between the river’s eastern arms. A puzzle went round: could you take a walk that crosses every bridge exactly once?
Nobody could find one. In 1736 the Swiss mathematician Leonhard Euler showed that nobody ever would, and he did it without trying a single route.
Only the connections matter
Euler noticed that almost everything about the town is irrelevant. The shape of the island, the length of the streets and where on a bank you stand make no difference. All that matters is which pieces of land each bridge joins.
So shrink each piece of land to a dot and draw each bridge as a line between two dots. What is left is a graph: a set of points, called vertices or nodes, joined by lines, called edges. Choose Graph under Turn the town into a graph and the model town turns into exactly this drawing, with island A in the middle, the banks B and C, and the eastern land D.
Counting the bridges at each piece of land
Now think about a walk passing through a piece of land. Every time it arrives over one bridge, it must leave over another. So the bridges at a piece of land the walk merely passes through are used up in pairs, and their number must be even. The number of edges at a vertex is called its degree.
The only places allowed an odd degree are where the walk starts and where it ends. That means:
- If every degree is even, a walk can cross every edge once and finish where it began, a circuit.
- If exactly two degrees are odd, a walk can cross every edge once, but it must start at one odd vertex and end at the other.
- If more than two are odd, no such walk exists.
In Königsberg the island has five bridges and each of the other three pieces of land has three. All four degrees are odd, so the walk is impossible. In the scene the walker crosses as many bridges as it can, and the bridge it cannot reach stays glowing red.
Try it: set Bridges to 7, as in 1736, and choose Graph under Turn the town into a graph: every dot glows orange. Then set Bridges to 6 and to 9 and watch the orange dots disappear.
There can never be exactly one odd vertex. Each edge has two ends, so the degrees always add up to twice the number of edges, an even number, and the odd ones must come in pairs.
Finding the walk
Euler’s counting tells you when a walk exists. Actually finding one takes a recipe, and a neat one was published in 1873 by the German mathematician Carl Hierholzer, who proved that Euler’s condition is enough as well as necessary. Start at an odd vertex if there is one, and keep walking along any unused edge until you get stuck. If edges are left over, go back to a vertex on your route that still has unused edges, walk a loop from there until you return, and splice the loop into your route. Repeat until every edge is used. The scene’s walker follows a route found exactly this way.
Walks that use every edge once are now called Euler paths and Euler circuits. The same reasoning plans routes for street sweepers, snowploughs and delivery rounds that must cover every street, and graphs in general describe anything made of connections: road maps, electrical circuits, molecules, friendships and the links between web pages.
What this model leaves out
The town is a simplified model. The river, the land and the bridge positions are drawn to show which land each bridge joins, not to match old maps, and the eighth and ninth bridges are invented to show what changes. A real stroller could also cross by boat; the puzzle forbids that, and so does the model. Finally, Euler worked with letters for the pieces of land and counts of bridges rather than a drawing of dots and lines; the graph picture is the modern way of showing his idea.