The Seven Bridges of Königsberg

In the early 18th century, in the city of Königsberg in Prussia (now Kaliningrad), a problem was discussed among the people. Königsberg was divided into four landmasses by the Pregel River flowing through its center, and a total of seven bridges connected these landmasses. The city dwellers wondered whether it was possible to take a walk crossing each bridge exactly once. The striking feature of the problem was that no specific starting or ending point was specified, yet the condition required using each bridge only once.

In 1736, the Swiss mathematician Leonhard Euler began working on this problem. To solve it, he developed a model independent of the physical map. Euler represented the four landmasses of the city as nodes and the bridges as lines connecting these nodes. Using this structure, he arrived at a solution.

class=\

class=\

1. In the Königsberg bridges problem, there is no designated starting or ending node.
2. If one begins in any region, to use all bridges, one must exit a region after entering it.
3. For a person to complete the tour without a designated start or end, all intermediate nodes must have an even degree.

class=\

If one begins by crossing a bridge out of a region and must return to the same region at the end, all bridges connecting other regions must be traversed, and the journey must conclude in the starting region. Therefore, every region must have an even degree.

class=\

class=\

At least one of the starting or ending regions must have an odd degree, while all other nodes must have an even degree. From this, it follows that in problems where the start and end points differ, there can be at most two nodes with an odd degree.

class=\

class=\

In conclusion the people of Königsberg were right in being unable to find such a path, because the regions separated by the Königsberg bridges contain more than two regions with an odd number of bridges. Therefore, it is impossible to cross each bridge exactly once.

The methods Euler developed to solve this problem laid the foundations for a mathematical field later known as “Graph Theory.” This field is now applied in numerous areas, from computer science to social network analysis. “We can define nodes as cities and the edges connecting them as major road links between cities. In a chemical molecule, nodes represent atoms and edges represent chemical bonds between them. A sociologist can represent the behaviors and interactions of a group of people using a graph. Highway maps, heating and water systems, shapes of certain elements, family trees, blood circulation, electrical circuits, computer applications and modeling, genetics, environmental science, archaeology, art, music, and others also involve such structures.”^【1】