Königsberg Bridge Problem

The foundations of network science is graph theory, and at the beginning of graph theory stands one problem that started it all: The Königsberg Bridge Problem. The problem poses a simple challenge:

No, you can’t. Some of the historical bridges in Königsberg don’t even exist anymore. But could you have done it, if you had lived in historical Königsberg? Could you do it in your city today? Thinking about this leads down a fascinating rabbit hole.

Eulerian Walks

The map of Königsberg shown above was published in 1652 and is commonly attributed to “Merian-Erben”. But Merian-Erben isn’t a person. Erben means “heirs” in German and Merian-Erben are the heirs of Matthäus Merian, a famous Swiss engraver working in Frankfurt, Germany. When Merian died in 1650, the map of Königsberg was found among his estate, and two years later his heirs collectively published it with the attribution “Merian-Erben.”

Historical Königsberg looks like a pretty town, doesn’t it. Wouldn’t it be nice to go for a little walk on a Sunday afternoon that crosses every bridge exactly once? But can you? It would take another eighty years till this puzzle was solved.

Today we say that a walk that crosses every bridge in a city exactly once is an eulerian walk. The name honours Leonard Euler who solved the Königsberg bridge problem in 1736 and in doing so created a new branch of mathematics.

Euler was well aware that the problem could be solved by carefully listing all possible walks and then checking each one in tern to see if it was a solution, he writes:

The particular problem of the seven bridges of Königsberg could be solved by carefully tabulating all possible paths, thereby ascertaining by inspection which of them, if any, met the requirement. This method of solution, however, is too tedious and too difficult because of the large number of possible combinations, and in other problems where many more bridges are involved it could not be used at all. When the analysis is undertaken in the manner just described it yields a great many details that are irrelevant to the problem; undoubtedly this is the reason the method is so onerous. Hence I discarded it and searched for another more restricted in its scope; namely, a method which would show only whether a journey satisfying the prescribed condition could in the first instance be discovered; such an approach, I believed, would be much simpler.

Leonard Euler, Solutio problematis ad geometriam situs pertinentis, 1736.

Even in 1736 it would have been possible to solve the problem in this way in an afternoon: With only seven bridges, there are only 2520 paths that need to be tabulated and checked. But Euler’s idea is much better. It hints at tow powerful principle: Simple models and Economy of Information.

Simple Models

Euler’s first insight was that everything becomes easier when we eliminate the needless information. Merian’s map is nice, but all the details it shows are not relevant to the problem, and they obscure the view of the bridges.

Problems become easier when we focus on the bare necessities needed to capture their essence. This is the reason why we make models, to simplify a world that is otherwise to complicated to understand.

Euler’s map of Königsberg, shown above, shows only the elements that are necessary to capture the essence of the problem: the land masses and the bridges connecting them.

Building on Euler’s work, there is an even easier way in which we can represent the structure of historical Königsberg. We represent the different land masses by the nodes of a network and we represent the the bridges connecting them as links between these nodes.

Economy of Information

The other principle at which Euler hints is Economy of Information. In a nutshell: If we pose a question for which a typical answer would contain a lot of information, the answer will often be difficult to find. We need to pay a price for the information that we demand. A longer answer will take more work to find. Conversely if we ask a question that can be answered more quickly, then there is often an easy way to find the answer.

If we ask how to walk across every bridge exactly once, the answer we are asking for is the walk itself, e.g. a set of instructions containing the sequence of bridges that we cross. By contrast if we ask is a walk possible at all, the answer is a simple yes or no.

Euler focussed on the question why a walk that crosses every bridge exactly once might not exist. To discuss failure we need the concept of node degree. In our network representation of the city, each network node represents a landmass and each link represents a bridge. In network science the degree of a node is the number of links connecting , so in our case the degree of each landmass is the number of bridges connecting to it.

The Truth about Königsberg

In the the Königsberg network one node has degree five and three nodes have degree three, so we have four nodes of odd degree. This proves that that no eulerian walk exists—we cannot go on a walk that crosses each bridge exactly once.

Today the bridge problem is often portrayed as a serious problem that people wanted an answer for, but this is not what it was. In the eighteenth century their was no internet, no youtube, no social media. Instead people turned to books and wrote letters. Many, many letters. Even Kings and Queens of the time were keeping up with recent developments in science and mathematics, and members of the high society would challenge each other to solve puzzles. Occasionally they might send someone an insolvable puzzle as a joke. The most notorious one of these joke puzzles was the Königsberg bridge problem—a form of 18th century trolling.

A good troll problem must not only be unsolvable, but it must also seem simple to ensnare its victims. Indeed, the Königsberg bridge network, is the smallest, simplest network for which there is no solution without this being immediately obvious. To be unsolvable a network must have at least four nodes, each of them with an odd degree. We don’t want any node to have degree one, because that put people immediately on the right track to the solution. So far the simplest network that meets these criteria, would have four nodes of degree three. But there is only one such network, and it forms a tetrahedron, a network that is so symmetric that we by exploiting the symmetry we can reduce the number of walks that need to be tried to just two—clearly not good for trolling. The next simplest unsolvable network has three nodes of degree three and one node of degree five and it is the Königsberg bridge graph.

Euler would not be trolled by it. Instead he proved that the bridge problem was unsolvable in such an elegant way that everybody could understand the proof. Because the problem was already notorious the news of the proof spread like wildfire throughout Europe. Essentially by thinking about the city as a system of nodes and links Euler had invented a new way of describing the world with mathematics—a new way of modelling. Euler said he had wanted a proof that mirrored the elegance of geometry, and he called his new way of thinking Geometria Situs, the geometry of position. Later J. J. Sylvester coined another name for this kind of mathematics: Graph Theory, and today many would call it Network Science.