The importance of the Seven Bridges of Königsberg

Many of the most advanced mathematical concepts we have today have very humble origins. And this is arguably no more demonstrable than in the case of graph theory, which emerged from a simple problem of crossing a few bridges. The story of the Seven Bridges of Königsberg saw the progress of logical conclusions to a system of mathematical analysis that would become graph theory, and which would lay the ground for the idea of topology in the process. Here’s why these bridges have proven so important for maths.

Königsberg (now known as Kaliningrad) was a city in Prussia. It was set on both sides of the Pregel River, and it included two large islands – Kneiphof and Lomse – that were connected to each other, and to the mainland portions of the city, by seven bridges. According to folklore, the citizens wondered whether it was possible to take a walk through the town in such a way that each bridge would be crossed exactly once. For the sake of the puzzle, reaching an island or mainland bank other than via one of the bridges was forbidden, as was accessing any bridge and not crossing to its end.

The answer may seem a logical one, but it was the mathematician Leonard Euler who formalised it. In 1735, he presented a solution to the problem, concluding that such a walk was impossible. He had never lived in Königsberg, but he realised that the choice of route was actually completely irrelevant to the problem – the only thing that matter was the sequence of bridges crossed. He reformulated the question, stripping away all features except the land masses and the bridges connecting them, and he devised a wonderful solution.

In a single encounter with a specific landmass, other than the initial or terminal one, two different bridges must be accounted for – one for entering the landmass and one for leaving it. Thus, each such landmass must serve as an endpoint of a number of bridges equalling twice the number of times it is encountered during the walk. Therefore, each landmass, with the possible exception of the initial and terminal ones if they are not identical, must serve as an endpoint of an even number of bridges. However, for the landmasses of Königsberg, one island is connected by five bridges, and the other and the two mainland banks are connected by three. The walk is therefore impossible.

It would be nearly 150 years later before mathematicians would formalise the Königsberg bridge problem in terms of the emerging graph theory. In modern terminology, the islands are nodes or vertices, and the bridges are arcs or edges. The degree of a vertex specifies the number of edges incident to it. Euler’s assertion that a graph that would fulfil the bridge problem has at most two vertices of odd degree (a formal reformulation of his conclusion) was thus the first theorem of graph theory. Such walks are now known as Eulerian paths in the mathematician’s honour.

The ways that this approach influenced graph theory are clear, but Euler’s reasoning would also presage the emergence of topology, the study of the continuous properties of geometric objects. Euler’s conclusion that the actual layout of Königsberg was immaterial is often considered a precursor to the ways that topologists are not concerned with the rigid shape of objects.

Konigssberg was bombed in World War II, and two of the bridges did not survive. Two more would be demolished, and replaced with a modern highway – those seven bridges are now five, but that has led to an interesting development. Two of the nodes now have degree two, and the others degree three, so it is now possible to complete a walk that satisfies the original problem. It’s an amusing development, one showing the wonderful relationship between abstract mathematical problems and real-world developments.