The Seven Bridges of Königsberg

People living in the 18th-century city of Königsberg have been solving a puzzle for a long time: the Pregola River flows through the city, forming two islands. There are seven bridges across the river to the islands. Is it possible to cross all the bridges in one Sunday walk, but only once each? Let's take a look at how the bridges over the river were built:

Is it possible for us to start our walk at some point and cross all the bridges just once? We can try it, starting at the bottom left and working our way up and then gradually to the right, like this:

We can see that we've crossed six of the seven bridges, and we've missed one of the bridges. We can try another way...

Again, we've only passed six of the seven bridges of our King's Bridge. It almost seems like it's impossible to walk across every bridge just once. One day the famous mathematician Leonhard Euler came across this problem. What famous - Euler was a mathematical legend, after whom Euler's number is even named. Euler thought he'd crack the puzzle. He started by marking the islands or parts of the city to and from which bridges led:

Euler now made the following reasoning: if an island has an even number of bridges leading to it, we can cross these bridges in one walk, wherever we start. In short, we arrive on the island by one bridge and leave by another - the number of bridges we can no longer cross has been reduced by two. In order to use one bridge to get to the island and the other to leave, we need two bridges. If six bridges lead to the island, we visit the island three times. For example, suppose there were four bridges leading to island B as follows:

Then we can walk across all the bridges in one Sunday walk, wherever we start. Try it! I have marked one path in the picture. But suppose there was another bridge leading to island B from island D:

We can see that the path we have chosen will not allow us to cross all the bridges just once. We would have to go back to island B by one of the bridges and then go to island D. But we can choose another way. We can start our walk on island B and then we are able to cross all the bridges just once:

We started our walk on island B, went up to territory A, then took the bridge back to B, to territory C, then back to island B, and finally to island D. Thus, if we start on a bridge that has an odd number of bridges, we are able to cross all of its bridges just once. Or we can go the other way around - we can start on island D and end on island B.

So Euler noticed that in order to be able to cross all the bridges just once, it must hold that either all the islands must have an even number of bridges, or there can be two islands that have an odd number of bridges - we start on one island with an odd number of bridges and end on the other. All other islands must have an even number of bridges. If we look at the original seven bridges in King:

we see that each island has an odd number of bridges! Island A has 3, B has 5, V has 3, and D also has 3. Therefore, the puzzle has no solution - there is no way we could have crossed all seven bridges just once on one Sunday walk. If we knocked down any of the bridges, suddenly the riddle would have a solution. For example, let's knock down one of the bridges between islands B and C:

We see that suddenly island B has four bridges and island C has two bridges. Islands A and D have the same number of bridges. Suddenly we 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 just once. In the picture we started on island A and ended on island D.

So Leonhard Euler solved another famous mathematical problem and more or less laid the foundations for what we nowadays call graph theory, and by his reckoning, "the walk where we cross all the bridges just once" is called an Eulerian graph in graph theory parlance.