The Problem That Started Graph Theory
In 1736, Leonhard Euler tackled a recreational puzzle: can you walk through the city of Königsberg, crossing each of its seven bridges exactly once? By abstracting the city into a graph — landmasses as vertices, bridges as edges — Euler proved the walk was impossible. His key insight: such a traversal requires that at most two vertices have an odd number of edges. All four Königsberg vertices had odd degree, so no solution existed. This paper is universally regarded as the birth of graph theory.
Eulerian Paths and Circuits
Euler's theorem gives a complete characterization: a connected graph has an Eulerian circuit (returning to the start) if and only if every vertex has even degree. It has an Eulerian path (starting and ending at different vertices) if and only if exactly two vertices have odd degree. Hierholzer's 1873 algorithm finds such paths in O(E) time by stitching together smaller circuits, making it one of the most efficient graph algorithms known.
The Hamiltonian Contrast
While Eulerian paths visit every edge once, Hamiltonian paths visit every vertex once. Despite the apparent similarity, the computational difference is staggering. No simple degree condition characterizes Hamiltonian graphs, and no polynomial-time algorithm is known — the decision problem is NP-complete. Sufficient conditions exist (Dirac's theorem: if every vertex has degree ≥ V/2, a Hamiltonian cycle exists), but they are far from necessary. This contrast beautifully illustrates the P vs NP divide.
From Bridges to DNA Sequencing
Eulerian paths have powerful modern applications. In genome sequencing, DNA is shattered into short overlapping fragments. By constructing a de Bruijn graph where fragments are edges, finding an Eulerian path through this graph reconstructs the original DNA sequence. This approach, used by assemblers like Velvet and SPAdes, processes billions of fragments efficiently because Eulerian path algorithms run in linear time — a direct practical payoff from Euler's 1736 insight.