Euler and Hamilton: walking through graphs
Some of the oldest questions in graph theory ask whether you can travel through a network visiting every edge, or every vertex, exactly once.
The bridges of Konigsberg
In 1736, Leonhard Euler asked whether one could walk through the city of Konigsberg crossing each of its seven bridges exactly once. He modelled land areas as vertices and bridges as edges, and showed it was impossible. This is usually considered the birth of graph theory.
Euler circuits and trails
An Euler circuit uses every edge exactly once and returns to the start; an Euler trail uses every edge once but may end elsewhere. Euler's theorem: a connected graph has an Euler circuit exactly when every vertex has even degree, and an Euler trail exactly when exactly 0 or 2 vertices have odd degree. Konigsberg had four odd vertices.
Why even degrees matter
Each time a walk passes through a vertex, it uses one edge in and one edge out, consuming two from that vertex's degree. So every vertex except the start and end needs even degree. This short argument is the whole proof of the necessity part of Euler's theorem.
Hamiltonian paths and cycles
A Hamiltonian cycle visits every vertex exactly once and returns to the start. Unlike Euler circuits, there is no simple test for Hamiltonian cycles; deciding whether one exists is NP-complete, believed to require huge amounts of computation for large graphs. Dirac's theorem gives a sufficient condition: if every vertex has degree at least \(n/2\), a Hamiltonian cycle exists.
The travelling salesperson problem
Find the shortest route visiting every city once and returning home: a weighted Hamiltonian cycle. It is central to logistics, chip design, and DNA sequencing. Exact solutions are infeasible for large inputs, so practical solvers use clever heuristics that find near-optimal routes.
Worked example
A graph has vertices with degrees 2, 4, 4, 3, 3, 2. Exactly two vertices are odd, so it has an Euler trail starting at one odd vertex and ending at the other, but no Euler circuit. A street-sweeper route covering every street once would therefore have to start and finish at different places.
Applications
Euler circuits plan routes that cover every street once: snowploughs, postal delivery, and street cleaning (the Chinese postman problem). Hamiltonian cycles and the travelling salesperson problem plan delivery routes visiting every customer.
Common mistakes
Confusing Euler (every edge) with Hamilton (every vertex). Forgetting that the graph must be connected for Euler's theorem. Assuming there is an easy test for Hamiltonian cycles.
Key takeaways
Euler circuits exist exactly when a connected graph has all even degrees; Euler trails when 0 or 2 vertices are odd. Hamiltonian cycles visit every vertex once and have no easy test. The travelling salesperson problem seeks the cheapest Hamiltonian cycle and is solved in practice by heuristics.
Flashcard
Euler's 1736 problem
Check your understanding
A connected graph has all vertices of even degree. It must have: