The seven bridges of Königsberg

For a long time, the people of Königsberg in the 18th century puzzled over a riddle: the River Pregel flows through the city and forms two islands. A total of seven bridges lead across the river to the islands. Is it possible, on a single Sunday walk, to cross all the bridges, but each exactly once? Let’s look at how the bridges crossed the river:

Is it possible to start our walk somewhere and cross all the bridges exactly once? We can try. We start at the bottom left and work our way up and then gradually to the right, like this:

We can see that we crossed six of the seven bridges and missed one. We can try a different route…

Again we crossed only six of the seven bridges of our Königsberg. It almost looks as if it is impossible to cross every bridge exactly once on one walk. One day the famous mathematician Leonhard Euler came across this problem. And not just famous – Euler was a true legend of mathematics, and even Euler’s number is named after him. Euler decided that he would crack this riddle. He began by labelling the individual islands, or parts of the city, to and from which the bridges led:

Euler now reasoned as follows: if an even number of bridges lead to an island, we can cross these bridges during one walk, wherever we start. Simply put, we arrive on the island by one bridge and leave by another – the number of bridges still left to cross goes down by two. To arrive on an island by one bridge and leave by another, we need two bridges. If six bridges lead to an island, we visit the island three times. For example, imagine that four bridges led to island B like this:

Then on one Sunday walk we can cross all the bridges, wherever we start. Try it! In the picture I have marked one route. Now imagine that there were one more bridge leading to island B, from island D:

We can see that the route we chose does not let us cross all the bridges exactly once. We would have to return to island B by one of the bridges and then cross to island D. But we can choose a different route. We can start our walk on island B, and then we are able to cross all the bridges exactly once:

We started our walk on island B, went up to area A, then back across a bridge to B, on to area C, then back to island B and finally to island D. So if we start on an island that has an odd number of bridges, we are able to cross all of its bridges exactly once. Or we can do it the other way round – we can start on island D and finish on island B.

So Euler noticed that for it to be possible to cross all the bridges exactly once, either all the islands must have an even number of bridges, or there can be two islands with an odd number of bridges – we start on one island with an odd number of bridges and finish on the other. All the other islands must have an even number of bridges. If we look at the original seven bridges in Königsberg:

we see that every island has an odd number of bridges! Island A has 3, B has 5, C has 3 and D also has 3. That is why the riddle has no solution – it is not possible to cross all seven bridges exactly once on a single Sunday walk. If we demolished any one of the bridges, the riddle would suddenly have a solution. Let’s demolish, for example, one of the bridges between islands B and C:

We can see that island B suddenly has 4 bridges and island C has two bridges. The number of bridges on islands A and D has not changed. Now we suddenly have two islands with an even number of bridges and two islands with an odd number of bridges. If we start our walk on one of the islands that have an odd number of bridges, we can cross all the bridges exactly once. In the picture we started on island A and finished on island D.

So Leonhard Euler solved another famous mathematical problem and more or less laid the foundations of what we now call graph theory, and in his honour a graph in which it is possible to traverse all the edges exactly once is called, in the language of graph theory, an Eulerian graph.