Hamiltonian Cycle via Backtracking (Graph 6 vertices A-F)

Adjacency matrix (undirected):

• A: B,C,F
• B: A,C,D
• C: A,B,E
• D: B,E
• E: C,D,F
• F: A,E (also C? matrix shows F-C 1 → F:C yes, but table: F row C=1)
  Edges: AB,AC,AF,BC,BD,CE,DE,EF,FC (and symmetric).

Backtracking Algorithm

HamCycle(path[0..V-1], pos):
  if pos==V: return edge path[V-1]--path[0] exists
  for v=1..V-1:
    if not used[v] and edge path[pos-1]--v exists:
      path[pos]=v; used[v]=true
      if HamCycle(path,pos+1) return true
      used[v]=false // backtrack
  return false

Start path[0]=A.

Search Tree (choose smallest lex order)

1. Path [A] → try B:

• [A,B] → try C (A used):
  • [A,B,C] → neighbors E (A,B used) → [A,B,C,E]:
    • [A,B,C,E] → neighbors D,F; try D:
      • [A,B,C,E,D] → neighbors B only (used) → dead end → backtrack D
    • try F:
      • [A,B,C,E,F] → neighbors A,C? Actually F neighbors A,E,C → only A unvisited but need visit D still → dead (no D) → backtrack
  • backtrack E → no other neighbor → backtrack C
• [A,B] → try D:
  • [A,B,D] → D→E → [A,B,D,E]:
    • [A,B,D,E] → try C:
      • [A,B,D,E,C] → C neighbors A,B,E (all used) → need F but no edge C-F? Actually C-F edge exists (F-C=1) but F not visited! Let's see: C connected to F via F-C=1 → C-F exists. But path has [A,B,D,E,C] → from C we can go to F:
      • [A,B,D,E,C,F] → check edge F-A exists? Yes F-A=1, all 6 vertices visited → Cycle A-B-D-E-C-F-A? Need verify edges: B-D yes, D-E yes, E-C yes, C-F yes, F-A yes → valid Hamiltonian cycle!

Solution found: A → B → D → E → C → F → A (also reverse A-F-C-E-D-B-A).
Alternative cycles also exist: A-C-E-D-B-A? Check A-C yes, C-E yes, E-D yes, D-B yes, B-A yes but need include F → not. Another: A-F-E-D-B-C-A? F-E yes, E-D yes, D-B yes, B-C yes, C-A yes → A-F-E-D-B-C-A also valid but ordering different start. Our path A-B-D-E-C-F-A is valid Hamiltonian cycle visiting each vertex exactly once and returning to A.

If backtracking explores lex order, first found may be A-B-C-E-F-? Actually earlier branch failed; the successful is A-B-D-E-C-F-A.

Complexity

Worst $O(V!)$ backtracking, pruning by degree; with bounding better than naive $O(V^V)$.