Skip to content
doubtly

1 answer

A Hamiltonian cycle is a cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

Definition. For a graph \(G = (V, E)\) with \(n\) vertices, a Hamiltonian cycle is a path \(v_1, v_2, \dots, v_n, v_1\) where all \(v_i\) are distinct and every consecutive pair (including \(v_n, v_1\)) is joined by an edge. A graph that has one is called a Hamiltonian graph. (Compare: an Euler circuit uses every edge once; a Hamiltonian cycle uses every vertex once.)

Example. In a square A–B–C–D–A with one diagonal A–C, the cycle A → B → C → D → A is Hamiltonian.

Finding it by backtracking. No fast (polynomial) algorithm is known; the problem is NP-complete. The usual syllabus method is backtracking:

  1. Keep an array x[1..n]; fix x[1] = starting vertex.
  2. For position k, try each vertex v in turn. Accept it only if (a) there is an edge from x[k-1] to v, and (b) v has not been used yet.
  3. If k = n, also check that there is an edge from x[n] back to x[1]; if yes, print the cycle.
  4. If no vertex fits at position k, go back (backtrack) to position k-1 and try its next vertex.
Hamiltonian(k):
  for each vertex v:
    if adj[x[k-1]][v] and v not in x[1..k-1]:
      x[k] = v
      if k == n:
        if adj[x[n]][x[1]]: print x
      else:
        Hamiltonian(k+1)

State space tree. The root is the start vertex; each level adds the next vertex of the path. A branch is cut (bounded) as soon as a vertex is repeated or no edge exists, which saves a lot of work compared with trying all \(n!\) orders.

Complexity. Worst case \(O(n!)\) since in the worst case many permutations are explored.

Applications. Travelling salesman–type route planning, circuit design, and scheduling problems where each task/place must be visited exactly once.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.