Seven Bridges of Königsberg
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.
Euler's insight — that only the degrees of the vertices matter, not the geometric layout — became the seed of graph theory. His general criterion, now called the Eulerian circuit theorem, states that a connected graph has a closed walk using every edge exactly once if and only if every vertex has even degree; an open walk using every edge exactly once (an Eulerian path) exists if and only if exactly zero or two vertices have odd degree.
References
- Leonhard Euler (1741). Solutio problematis ad geometriam situs pertinentis · DOI:10.1090/spec/098/33
- Norman L. Biggs, E. Keith Lloyd, Robin J. Wilson (1976). Graph Theory 1736–1936