Seven Bridges of Königsberg

The Seven Bridges of Königsberg is a historical problem in mathematics. The negative resolution of the problem by Leonhard Euler led to the advent of graph theory and topology.

The city of Königsberg in Prussia (now Kaliningrad, Russia) laid on either sides of the Pregel River and included two large islands—Kneiphof and Lomse—which were connected to each other, or to the two mainland portions of the city, by seven bridges.

The problem was to to design a walk through the city crossing every bridge only once.

Solutions involving either

1. reaching an island or mainland bank other than via one of the bridges, or
2. accessing any bridge without crossing to its other end are explicitly unacceptable.

The branch of geometry that deals with magnitudes has been zealously studied throughout the past, but there is another branch that has been almost unknown up to now; Leibnitz spoke of it first, calling it the geometry of position” (geometria situs). This branch of geometry deals with relations dependent on position alone, and investigates the properties of position; it does not take magnitudes into consideration, nor does it involve calculation with quantities. But as yet no satisfactory definition has been given of the problems that belong to this geometry of position or of the method to be used in solving them.

First, Euler pointed out that the choice of route inside each land mass is irrelevant. The only important feature of a route is the sequence of bridges crossed. This allowed him to reformulate the problem in abstract terms eliminating all features except the list of land masses and the bridges connecting them. In modern terms, one replaces each land mass with an abstract “vertex” or node, and each bridge with an abstract connection, an “edge”, which only serves to record which pair of vertices (land masses) is connected by that bridge. The resulting mathematical structure is called a graph.

Next, Euler observed that (except at the endpoints of the walk), whenever one enters a vertex by a bridge, one leaves the vertex by a bridge. In other words, during any walk in the graph, the number of times one enters a non-terminal vertex equals the number of times one leaves it. Now, if every bridge has been traversed exactly once, it follows that, for each land mass (except for the ones chosen for the start and finish), the number of bridges touching that land mass must be even (half of them, in the particular traversal, will be traversed “toward” the landmass; the other half, “away” from it). However, all four of the land masses in the original problem are touched by an odd number of bridges (one is touched by 5 bridges, and each of the other three is touched by 3). Since, at most, two land masses can serve as the endpoints of a walk, the proposition of a walk traversing each bridge once leads to a contradiction.

In terms of graph theory, two of the nodes now have degree 2, and the other two have degree 3. Therefore, an Eulerian path is now possible, but it must begin on one island and end on the other.

Topological aspect shall be discussed in detail in another post.