Seven Bridges of Königsberg

In graph theory, the problem of the seven bridges of Königsberg was first solved by Leonhard Euler. In the history of mathematics, it is one of the first problems in graph theory to be formally discussed, and also, as graph theory can be seen as a part of topology, one of the first problems in topology. (The field of combinatorics also has a claim on graph theory, but combinatorial problems had been considered much earlier.)

The city of Königsberg (now Kaliningrad) was set on the river Pregel, and included two large islands which were connected to each other and the mainland by seven bridges, as in the schematic figure below:

The question was whether it was possible to walk a route that crossed each bridge exactly once, and returned to the starting point. In 1736, Euler proved that it was not possible. In proving the result, he formulated the problem in terms of abstract graphs, with the case of Königsberg corresponding to the following graph:

.

Euler showed that a path of the desired form is possible if and only if there are no nodes (dots in the picture above) that have an odd number of edges touching them. Such a walk is called an Eulerian circuit or an Euler tour. Since the graph corresponding to Königsberg has four such nodes, the path is impossible.

If the starting point does not need to coincide with the end point there can be either zero or two nodes that have an odd number of edges touching them. Such a walk is called an Eulerian trail or Euler walk.

This is a map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the waterways with blue and the bridges with green.

The difference between the actual layout and the schematic above is a good example of the idea that topology is not concerned with the rigid shape of objects.

There is a social aspect to the problem of the Königsberg bridges. Circa 1750, the prosperous and educated townspeople would walk about on Sundays and try to solve the problem. Perhaps it is an urban legend, but interesting.