Hamiltonian Cycle
A Hamiltonian cycle (or Hamiltonian circuit) is a closed path in a graph that visits every vertex exactly once before returning to the starting vertex. Unlike the Euler path (which covers every edge), the Hamiltonian cycle covers every vertex. Determining whether a Hamiltonian cycle exists in an arbitrary graph is an NP-complete problem, making it one of the central challenges in computational complexity and combinatorial optimisation (e.g., the Travelling Salesman Problem).
Worked Example
Problem
In a complete graph K₄ with vertices {A, B, C, D} and all 6 edges present, find all distinct Hamiltonian cycles.
Solution
Step 1: A Hamiltonian cycle visits all 4 vertices and returns to start. Step 2: Fix starting vertex A (to avoid counting rotations). List permutations of {B, C, D}: Cycle 1: A → B → C → D → A Cycle 2: A → B → D → C → A Cycle 3: A → C → B → D → A Step 3: Note that A→B→C→D→A and A→D→C→B→A are reverses (same cycle traversed backwards). So distinct cycles = 3!/2 = 3. Step 4: Verify each is a valid cycle (all edges exist in K₄ — yes, it's complete).
Answer
K₄ has 3 distinct Hamiltonian cycles: A-B-C-D-A, A-B-D-C-A, and A-C-B-D-A (and their reverses, which are the same cycles).
Comparison of Euler Path and Hamiltonian Cycle
| Feature | Euler Path | Hamiltonian Cycle | Notes |
|---|---|---|---|
| What it traverses | Every edge exactly once | Every vertex exactly once | Fundamentally different objectives |
| Start = End? | Only in Euler circuit | Yes (cycle) | Hamiltonian path: start ≠ end |
| Easy to detect? | Yes — check vertex degrees | No — NP-complete | No known efficient algorithm |
| Named after | Leonhard Euler (1736) | William Rowan Hamilton (1857) | Hamilton's Icosian game |
| Application | Postman routing, circuit design | Travelling Salesman Problem | TSP: find shortest Hamiltonian cycle |
| Existence condition | Degree-based criterion | No simple general criterion | Ore's/Dirac's theorems give sufficient conditions |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Euler Path
An Euler path (or Eulerian path) is a trail in a graph that visits every edge exactly once, without necessarily returning to the starting vertex. An Euler circuit (or Eulerian circuit) is an Euler path that begins and ends at the same vertex. A connected graph has an Euler path if and only if it has exactly zero or two vertices of odd degree; if two odd-degree vertices exist, the path must start and end at those vertices.
Graph Path
A path in a graph is a sequence of vertices in which each consecutive pair is connected by an edge and no vertex is repeated. The length of a path is defined as the number of edges it traverses. Paths are central to graph algorithms such as Dijkstra's shortest-path algorithm, breadth-first search, and depth-first search, which are used in navigation systems, network routing, and AI planning.
Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
The Hamiltonian cycle is named after Irish mathematician Sir William Rowan Hamilton (1805–1865), who in 1857 invented the Icosian Game — a puzzle sold as a toy involving finding a cycle along the edges of a dodecahedron that visits each of its 20 vertices exactly once. "Icosian" comes from Greek eikosi, "twenty."