Course contentsShow
← Mathematics
Lesson 2683 of 3,12153. Graph TheoryFree lesson

Hamiltonian Paths and Cycles: Definition and Examples

Define Hamiltonian paths (visiting every vertex once) and Hamiltonian cycles (closed Hamiltonian paths).

Hamiltonian Paths and Cycles: Definition and Examples

What you'll learn: You'll discover what it means for a path to visit every vertex in a graph exactly once, and when such a path forms a cycle.

The Core Idea

While Eulerian paths focus on traversing every edge exactly once, Hamiltonian paths focus on visiting every vertex exactly once.

A Hamiltonian path in a graph is a path that visits each vertex in the graph exactly one time. Think of it like a traveling salesperson who must visit every city on their map exactly once, but doesn't need to return home.

A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that returns to its starting vertex, forming a closed loop. This is like the salesperson's route when they must also return to their home city after visiting all others exactly once.

Key Differences from Eulerian Concepts

  • Eulerian: Focus on edges (traverse every edge once)
  • Hamiltonian: Focus on vertices (visit every vertex once)

Notably, determining whether a Hamiltonian path or cycle exists is much harder than for Eulerian paths—there's no simple degree-checking rule like Euler's Theorem.

Simple Example

Consider a graph with vertices {A, B, C, D} arranged in a square with edges A–B, B–C, C–D, D–A, and a diagonal A–C.

  • Hamiltonian path: A → B → C → D (visits all 4 vertices once)
  • Hamiltonian cycle: A → B → C → D → A (visits all 4 vertices and returns to start)

Not every graph has a Hamiltonian path or cycle. Finding them often requires systematic exploration or clever reasoning about the graph's structure.

Key Takeaway: A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does the same but returns to the starting vertex, forming a closed tour through all vertices.