Seven Bridges of Königsberg

Example

The city of Königsberg had four land areas, joined by seven bridges over the river Pregel. The problem asked for a walk that crosses each bridge exactly once.

Model each land area as a vertex and each bridge as an edge. This gives a connected multigraph with $4$ vertices and $7$ edges. The degrees of the vertices are $5$, $3$, $3$ and $3$. An Eulerian trail can have at most two vertices of odd degree, by the theorem on degrees along an Eulerian trail. Here all four degrees are odd, so the walk does not exist.

Remarks

Leonhard Euler solved the problem in 1736. His analysis is often seen as the start of graph theory. The problem has no solution even if the walk does not have to return to its start.

Explanations

L1 human

Each time a walk passes through a land area, it uses two bridges there, one to enter and one to leave. So a land area in the middle of the walk needs an even number of bridges. Königsberg had four land areas with an odd number of bridges.