Topology

One of the first problems known to have been considered that falls within the discipline of topology is called "The Seven Bridges of Königsberg". Königsberg was a city in Prussia, which is now Kaliningrad, Russia. There were seven bridges in the city crossing a river and connecting two islands to each other and both sides of the river (see figure 1). The question had been posed, "Is it possible to cross each of the bridges once without crossing any of them a second time?" The answer was given by Leonhard Euler in 1736. In short, it is not possible to cross all seven bridges exactly once.

Euler started by showing that the problem could be transformed into a set of three nodes connected by seven lines (see figure 2). The nodes represented each side of the river and the island. The lines each represented one of the bridges. The only way to travel from one node to another is via a line (a bridge).

To travel all the bridges from any node to another node without crossing one twice, either the node must be a start or end point and have an odd number of lines, or the node must not be a start or end point and have an even number of lines. But, since only two nodes can be the start and end points, and all the nodes have an odd number of lines, it is impossible to transverse all the lines (cross all the bridges) exactly once.