Question

Let G be an undirected complete graph, on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

• A. n!
• B. (n - 1)!
• C. 1
• D. $\frac{(n-1)!}{2}$

Answer 1

Answer: (C), (D)

$\frac{(n-1)!}{2}$

When vertices are labelled.
In a complete graph we can traverse the n vertices in any order and return to the starting vertex and form a Hamiltonian cycle. The number of such cycles will be n!. However, since circular rotations will have to ignored. Since for example $K_4$ with vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is same as 2-3-4-1 is same as 3-4-1-2 etc. we now get only (n - 1)! distinct Hamiltonian cycles. Further, the cycle 1-2-3-4 and 1-4-3-2 are also same (clock wise and anticlockwise).
So ignoring this orientation also we finally get $\frac{(n-1)!}{2}$ distinct Hamiltonian cycles which is option (d).

When vertices are unlabelled.
All the Hamiltonian cycles are formed which is isomorphic to each other. So only 1 Hamiltonian cycle will be the answer in this case.

So both option (c) and (d) are correct.