Seven Bridges of Königsberg

The Seven Bridges of Königsberg is the historical problem that gave birth to graph theory. In 1736, Euler proved that no route exists that crosses each of the seven bridges exactly once.

The problem

The city of Königsberg had seven bridges connecting four landmasses. Euler was asked: can you design a walk that crosses every bridge exactly once and returns to the starting point?

Euler''s insight

Euler modelled the city as a graph: landmasses as vertices, bridges as edges. He proved that such a closed route exists only if every vertex has even degree. Here, the four vertices (landmasses) have odd degrees, so no such route exists.

Legacy

This result is the origin of Eulerian paths and Eulerian circuits in graph theory. See Planar graphs and Euler''s Formula for related theory.