MathLabs

Seven Bridges of Königsberg

Solved, 1736Combinatorics and discrete mathematics
Statement

The city of Königsberg (now Kaliningrad) is built on the banks and two islands of the Pregel river, connected by seven bridges. Is it possible to walk through the city, crossing each of the seven bridges exactly once, without crossing any bridge twice?

Euler's original argument is a discrete parity argument rather than a proof phrased in the language of modern graph theory, which had not yet been invented; the terms 'graph', 'vertex' and 'edge' came later.

  1. Euler's degree argument (1736)Leonhard Euler, 1736Difficulty 2/5Advanced

References

  1. Leonhard Euler (1741). Solutio problematis ad geometriam situs pertinentis · DOI:10.1090/spec/098/33
  2. Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson (1976). Graph Theory 1736–1936