bridges of Königsberg
The bridges of Königsberg is a famous problem inspired by an actual place and situation. The solution of the problem, put forth by Leonhard Euler in 1736, is widely considered to be the first work of graph theory
and responsible for the foundation of the discipline.
The following figure shows a portion of the Prussian city of Königsberg. A river passes through the city, and there are two islands in the river. Seven bridges cross between the islands and the mainland:
Figure 1: Map of the Königsberg bridges.
The mathematical problem arose when citizens of Königsburg noticed that one could not take a stroll across all seven bridges, returning to the starting point, without crossing at least one bridge twice.
Answering the question of why this is the case required a mathematical theory that didn’t exist yet: graph theory. This was provided by Euler in his formative paper.
To solve the problem, we must translate it into a graph-theoretic representation. We model the land masses, , , and , as vertices in a graph. The bridges between the land masses become edges. This generates from the above picture the following graph:
Figure 2: Graph-theoretic representation of the Königsburg bridges.
At this point, we can apply what we know about Euler paths and Euler circuits. Since an Euler circuit for a graph exists only if every vertex has an even degree, the Königsberg graph must have no Euler circuit. Hence, we have explained why one cannot take a walk around Königsberg and return to the starting point without crossing at least one bridge more than once.
| Title | bridges of Königsberg |
|---|---|
| Canonical name | BridgesOfKonigsberg |
| Date of creation | 2013-03-22 12:33:47 |
| Last modified on | 2013-03-22 12:33:47 |
| Owner | akrowne (2) |
| Last modified by | akrowne (2) |
| Numerical id | 9 |
| Author | akrowne (2) |
| Entry type | Topic |
| Classification | msc 05C38 |
| Synonym | bridges of Koenigsberg |