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. He also showed that the problem could be viewed as a problem about 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 atmost two nodes that have an odd number of edged touching them. Such a walk is called an Eulerian Trail or Euler Walk.

Currently (March 2003) a map showing the actual layout of the seven bridges can be found at the external site http://www-gap.dcs.st-and.ac.uk/~history/Miscellaneous/Konigsberg. 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.