Skip to main content

Hamiltonian path and circuit with diagram

Short answer

A Hamiltonian path visits every vertex exactly once; a Hamiltonian circuit is a Hamiltonian path that returns to the start. A graph with a Hamiltonian circuit is Hamiltonian. No simple exact test exists; necessary conditions include connectivity and minimum degree ≥2. Dirac's condition (n≥3, deg(v) ≥ n/2) is sufficient.

Explain the Hamiltonian path and Hamiltonian circuit with the help of a diagram.

A Hamiltonian path is a simple path that passes through every vertex of the graph exactly once. A Hamiltonian circuit (cycle) is a simple cycle that passes through every vertex exactly once and ends where it started. A graph with a Hamiltonian circuit is called a Hamiltonian graph. Unlike in Euler paths, some edges may be left unused.

Diagram 1: a Hamiltonian circuit (and so also a path)

        a
       / \
      e   b           edges: ab, bc, cd, de, ea, plus chord ec
      |\  |
      | \ |           circuit: a, b, c, d, e, a
      d---c

The circuit a → b → c → d → e → a visits all 5 vertices once; the chord ec is not used.

Diagram 2: a Hamiltonian path but no circuit

   a ---- b ---- c
          |      |       edges: ab, bc, bd, cd
          d ------+

The path a → b → c → d (or a → b → d → c) visits every vertex once, so a Hamiltonian path exists. There is no Hamiltonian circuit because vertex a has degree 1, and a cycle needs degree at least 2 at every vertex.

No simple exact test is known. A Hamiltonian circuit needs a connected graph with no cut vertex and all degrees ≥ 2; Dirac's condition (n ≥ 3, deg(v) ≥ n/2 for all v) is sufficient.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →