Skip to content

Eulerian & Hamiltonian Paths

Eulerian path and circuit

An Eulerian circuit traverses every edge exactly once and returns to the start. An Eulerian path does the same without requiring a return.

Undirected connected graph:

  • Eulerian circuit: all vertices have even degree.
  • Eulerian path: exactly zero or two vertices have odd degree (odd vertices are path endpoints).

Directed: indegree equals outdegree for all vertices (circuit), or at most one vertex with out = in+1 and one with in = out+1 (path).

Finding one: Hierholzer’s algorithm — extend cycles greedily in \(O(|E|)\).

Hierholzer’s algorithm: maintain adjacency lists, walk unused edges from a stack, splice cycles—typically \(O(|E|)\) with multiset or linked structure for edge removal.

Hamiltonian problems use different machinery; Euler is polynomial.

Hamiltonian path

A Hamiltonian path visits every vertex exactly once. Deciding existence is NP-hard in general. Small \(n\) → bitmask DP or backtracking; special graphs (tournaments, grids) may have structure.

  • DFS / BFS — Hierholzer is DFS-like edge deletion
  • Bitmask DP — Hamiltonian path for small \(n\)