Crossing every bridge once: why Königsberg has no such walk, Euler's rule about odd nodes, where a walk must start, and when it comes back to the start.
Step 1 of 6 · The puzzle
Step 1 of 6
The puzzle
The people of Königsberg liked a Sunday walk through the town, and they asked: can you take a walk that crosses each of the seven bridges exactly once? Nobody found such a walk, but nobody proved there was none either. In the graph, the question is whether there is a walk that uses every edge once, without lifting the pencil. Such a walk is now called an Euler path. Predict.
Step 2 of 6
The best walk
Euler’s argument is simple. Each time a walk passes through a node, it enters by one edge and leaves by another, so it uses that node’s edges in pairs. A node that is not the start or the end must have an even degree. In Königsberg all four nodes are odd. When no complete walk exists, the walker in the Scene crosses as many bridges as it can, and the rest stay red.
Step 3 of 6
Fixing the town
One bridge more or one fewer flips the parity of its two ends. Change the number of Bridges and look for a setting where the walker crosses them all.
Step 4 of 6
Where to start
When exactly two nodes are odd there is a walk, but not from anywhere. Think about an odd node: its edges split into pairs of in and out, and there is always one left over.
Step 5 of 6
A circuit
If the walk ends exactly where it began, it is an Euler circuit. Then the start and the end use their edges in pairs as well.
Step 6 of 6
Euler’s rule
Euler showed that the two conditions, the parity and being connected, are also enough: if the graph is connected and the condition on the odd nodes holds, there is always a walk. It counts as the first result of graph theory, and it is still useful, for instance to plan the round of a rubbish lorry or a street sweeper that goes down every street once.
Loading the interactive version…
Loading the interactive version…
Each step sets up the Scene for you, and a control marked “fixed” stays put for that step.
Practice · Predict, then look
The people of Königsberg asked: can you walk through the town crossing each of the seven bridges exactly once? Predict.
Practice · Predict, then look
The people of Königsberg asked: can you walk through the town crossing each of the seven bridges exactly once? Predict.
Practice · Calculate
Without crossing any bridge twice, how many bridges at most can a walk cross in the Königsberg of 1736?
Practice · Calculate
Without crossing any bridge twice, how many bridges at most can a walk cross in the Königsberg of 1736?
Practice · Reach the target
Add or remove Bridges until there is a walk that crosses every bridge exactly once, and press Check.
Practice · Reach the target
Add or remove Bridges until there is a walk that crosses every bridge exactly once, and press Check.
Practice · Choose
With 8 bridges the degrees are A 5, B 4, C 4, D 3, and there is a walk over them all. Where must it start?
Practice · Choose
With 8 bridges the degrees are A 5, B 4, C 4, D 3, and there is a walk over them all. Where must it start?
Practice · Reach the target
An Euler circuit is a walk that crosses every edge once and returns to where it began. Change the Bridges until there is one, and press Check.
Practice · Reach the target
An Euler circuit is a walk that crosses every edge once and returns to where it began. Change the Bridges until there is one, and press Check.
Practice · Choose
A graph is connected. When does it have a walk crossing every edge exactly once?
Practice · Choose
A graph is connected. When does it have a walk crossing every edge exactly once?
Lesson complete. Every practice question here is done.