Introduction

In a complete undirected graph K_n, every pair of vertices is connected, so Hamiltonian cycles always exist when n is at least three. The counting question is a combinatorics problem, not a search problem in this special case. The final formula is simple, but understanding why the division factors appear prevents common overcounting mistakes.

Build the Count Step by Step

A Hamiltonian cycle visits every vertex exactly once and returns to start.

To count distinct cycles in K_n:

1. Fix one vertex as anchor to remove rotational duplicates.
2. Arrange the remaining n - 1 vertices in all orders.
3. Divide by two because each cycle has two traversal directions in undirected graph.

So number of cycles is:

• factorial of n - 1, divided by 2.

Equivalent formula:

• (n - 1)! / 2

This is valid for n >= 3.

Why Fixing One Vertex Works

Without fixing a start, each cycle can be rotated into n equivalent representations. Example cycle on vertices 1,2,3,4 can start at 1 or 2 or 3 or 4 and still represent same cycle.

Fixing one vertex removes those rotational duplicates immediately, leaving permutations of the remaining vertices only.

Then reverse-order duplication still remains:

• 1 -> 2 -> 3 -> 4 -> 1
• 1 -> 4 -> 3 -> 2 -> 1

These two are same undirected cycle, so divide by two.

Small-Value Table

Using (n - 1)! / 2:

• n = 3 gives 1 cycle.
• n = 4 gives 3 cycles.
• n = 5 gives 12 cycles.
• n = 6 gives 60 cycles.
• n = 7 gives 360 cycles.

Factorial growth is very fast, so counts become large quickly.

Direct Computation in Python

For counting only, use factorial.

1import math
2
3
4def hamiltonian_cycles_complete_graph(n: int) -> int:
5    if n < 3:
6        return 0
7    return math.factorial(n - 1) // 2
8
9
10for n in range(3, 9):
11    print(n, hamiltonian_cycles_complete_graph(n))

This is constant-time for practical purposes because computation is simple arithmetic.

Verification by Enumeration for Small n

To build intuition, enumerate cycles for very small graphs and deduplicate canonical forms.

1from itertools import permutations
2
3
4def enumerate_cycles_k_n(n: int):
5    if n < 3:
6        return []
7
8    start = 0
9    vertices = list(range(1, n))
10    seen = set()
11
12    for p in permutations(vertices):
13        cycle = (start,) + p
14        rev = (start,) + tuple(reversed(p))
15        key = min(cycle, rev)
16        seen.add(key)
17
18    return sorted(seen)
19
20
21for n in [3, 4, 5]:
22    cycles = enumerate_cycles_k_n(n)
23    print(n, len(cycles))

This brute-force verification is only for tiny n, but it confirms the formula conceptually.

Relationship to General Hamiltonian-Cycle Problems

In arbitrary graphs, counting Hamiltonian cycles is hard and generally requires exponential-time methods. Complete graphs are a rare case where symmetry gives closed-form count.

That distinction matters in interviews and algorithm design:

• For K_n, use formula directly.
• For sparse or constrained graphs, use search or dynamic programming techniques and expect much higher complexity.

Numeric Growth and Data Types

Counts exceed 32-bit integer limits quickly. Example:

• n = 14 gives (13)! / 2, already very large.

Languages with fixed-width integers may overflow. Use big-integer support when needed.

print(hamiltonian_cycles_complete_graph(20))

Python handles big integers natively, which is useful for combinatorics exploration.

Common Pitfalls

• Forgetting to divide by two for reverse traversal duplication. Fix by applying undirected symmetry correction.
• Forgetting rotational equivalence. Fix by anchoring one vertex before counting permutations.
• Applying complete-graph formula to non-complete graphs. Fix by verifying graph type first.
• Returning non-zero count for n less than three. Fix by handling small-n base cases explicitly.
• Overflowing fixed-width integers in other languages. Fix by using big-number libraries where required.

Summary

• In complete undirected graph K_n, Hamiltonian cycle count is (n - 1)! / 2 for n >= 3.
• Formula comes from anchored permutations and reverse-direction deduplication.
• Use direct factorial computation for exact counts.
• Enumerate only for small n when validating intuition.
• Do not reuse this closed-form result for general graph families.