The Seven Bridges of Königsberg

Origin of the Problem

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

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

(This image was designed using the Paint application)

(This image was designed using the Canva application)

Solution

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 the region after entering it.
3. For a person to complete the tour without a defined start or end, all intermediate nodes must have an even degree.

(This image was designed using the Paint application)

If the start and end city are the same:

When starting from a region by crossing one bridge, to return to the same region after traversing all bridges, every other region must be entered and exited an equal number of times. Therefore, every region must have an even degree.

(This image was designed using the Paint application)

(This image was designed using the Paint application)

If the start and end cities are different:

In such cases, at least one of the start or end regions must have an odd degree, while all other nodes must have an even degree. Thus, in problems where the start and end points differ, there can be at most two nodes with an odd degree.

(This image was designed using the Paint application)

(This image was designed using the Paint application)

In conclusion, the people of Königsberg were correct in their inability to find such a path, because the landmasses 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.

Some applications

The methods Euler developed to solve this problem laid the foundation for what later became the mathematical field known as "Graph Theory." This field is now applied in numerous areas, from computer science to social network analysis. "Points can represent cities, and the edges connecting these points can represent the main road connections between cities. In a chemical molecule, points represent atoms, and the edges connecting them represent the chemical bonds between these atoms. A sociologist can use a graph to represent the behaviors and interactions among a group of people. Graphs also appear in highway maps, heating and water systems, the shapes of certain elements, family trees, blood circulation, electrical circuits, computer applications and modeling, genetics, environmental science, archaeology, art, music, and other fields.^【1】 .