Euler Circuits & Hamilton Cycles

Two classic problems: Can we traverse every edge exactly once (Euler)? Can we visit every vertex exactly once (Hamilton)? Euler's problem has a complete characterization. Hamilton's problem is much harder — we have sufficient conditions (Dirac, Ore) but no complete characterization.

Learning Objectives

State and prove Euler's theorem for Euler circuits and Euler paths

Apply Dirac's and Ore's theorems as sufficient conditions for Hamilton cycles

Determine whether a given graph has an Euler circuit/path

Construct Euler circuits using Hierholzer's algorithm

Key Concepts

Euler Circuits & Paths

An Euler circuit traverses every edge exactly once and returns to the start. An Euler path traverses every edge exactly once but may end at a different vertex.

Euler proved a beautiful characterization: a connected graph has an Euler circuit iff every vertex has even degree.

-
Euler circuit: every vertex has even degree (and graph is connected)
-
Euler path: exactly 2 odd-degree vertices (path goes between them)
-
Hierholzer's algorithm constructs Euler circuits in $O(m)$ time
-
The original Seven Bridges of Königsberg problem: Euler showed no Euler path exists because 4 vertices had odd degree

Hamilton Cycles

A Hamilton cycle visits every vertex exactly once and returns to start. A Hamilton path visits every vertex exactly once.

Unlike Euler circuits, there is no simple necessary-and-sufficient condition. But we have useful sufficient conditions:

-
Dirac's condition: minimum degree $\geq n/2$ guarantees a Hamilton cycle
-
Ore's condition generalizes Dirac: $d(u) + d(v) \geq n$ for non-adjacent pairs
-
Neither condition is necessary — graphs can have Hamilton cycles without satisfying them
-
The Petersen graph has no Hamilton cycle (but does have a Hamilton path)
-
Deciding if a graph has a Hamilton cycle is NP-complete

W3: Trees & BFS W5: Bipartite Graphs & Coloring