The seven bridges of Koeningsberg

This problem is quite famous and very interesting. The primary reason why I decided to dedicate a page to it is very personal tough. I first read this problem while I was in my teens. Then, during my last year of university, I formally studied a property of certain graphs (called Eulerian graphs), with professor Francesco Maffioli. When he introduced the problem of the Bridges of Koenigsberg few lessons later, I was floored: how came that I failed to recognize that formal property as the solution of that old 'teen-age' problem?

The lesson I got from this experience taught me to always keep an open mind, even when studying very specific subjects: applications in several fields are not so rare.

The problem: Seven Bridges of Koenigsberg

Koenigsberg was a Prussian city. It was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk halfway onto the bridge and then turn around to come at it from another side).

Fig. 1: a schematic representation of the town, with river and bridges

A first approach to the solution

One can enumerate all the possible paths that a person could take by walking across the bridges. If he finds a path that satisfies the condition, then the problem has at least one solution (and he can show the path to prove it). On the contrary, if he's not able to find a path, after having tried all paths, then he can conclude that the problem has no solution.

The previous approach is correct, but quite long. Without counting all the paths ourselves (quite useless), we can at least provide an approximation.

Each bridge has two ends, so it can be travelled in both directions. That means we can start in 14 different positions. Once we cross a bridge, we have at least 2 other choices to make (4 if we end in the central isle). The reasoning goes on more or less like this until we can't proceed any more, or until we have crossed all the bridges. We can provide 14 * 2 * 2 * 2 = 112 as a lower bound to the number of paths. Actually the are more paths, but this gives us the idea of how long would it take at least.

So... have you found a solution?

Euler's solution

Euler's approach was abstract: in fact he laid the foundations of the graph theory, a branch of mathematics.

So let's represent the geometry of the problem as a graph. Each landmass is a vertex or node and each bridge is an edge or arc connecting two nodes. The number of arcs attached to a node is called degree of that node.

Fig. 2: the graph representation of the problem

To start with, Leonard pointed out that the choice of route inside each landmass is irrelevant. The only important feature of a route is the sequence of bridges crossed. But the key of his reasoning is the degree of a node.

Euler observed that (except at the endpoints of the walk) whenever one enters a node by a bridge, one leaves the node by a bridge. In other words, during any walk in the graph, the number of times one enters a non-terminal node equals the number of times one leaves it. Now if every bridge is traversed exactly once it follows that for each landmass (except possibly for the ones chosen for the start and finish), the number of bridges touching that landmass is even (half of them will be traversed "toward" the landmass, the other half "away" from it). In Koenigsberg, however, all the four landmasses in the original problem are touched by an odd number of bridges (one is touched by 5 bridges and the other three by 3). Since at most two landmasses can serve as the endpoints of a correct walk, the existence of a walk traversing each bridge once leads to a contradiction.

Thus Euler proved that the problem has no solution.

Going a little bit into formal details, Euler's argument showed that a walk of the desired form exists if and only if the graph is connected, and there are exactly zero or two nodes of odd degree. Such a walk is now called an Eulerian path in his honor. Furthermore, if there are nodes of odd degree, all Eulerian paths start at one of them and end at the other. Since the graph corresponding to historical Koenigsberg has four nodes of odd degree, it cannot have a Eulerian path. A graph is called Eulerian graph only if all nodes have even degree.

Second question: add bridges to make the problem solvable

With the help of Euler's genius, it becomes easy to modify the graph in order to be able to find a Eulerian path. It is sufficient to add a bridge between to nodes. These two nodes will have an even degree, while the other ones will be the start and the end of the walk respectively.

In Fig. 3 the added arc is red. I also represented a possible path on the graph with numbers: they indicated the order in which one has to travel the bridges.

Fig. 3: the modified graph, with a possible path outlined