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

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!/2
B. (n-1)!
C. (n-1)!/2
D. n!/(2n)

Accepted Answer

C, D -- both (n-1)!/2 and n!/(2n) equal the number of distinct Hamiltonian cycles in K_n. A Hamiltonian cycle visits every vertex exactly once and returns to the start. In K_n, we fix one vertex to avoid counting rotations, arrange the remaining n-1 vertices in (n-1)! ways, then divide by 2 because traversing the cycle in reverse gives the same cycle. The expressions (n-1)!/2 and n!/(2n) are algebraically identical, so both C and D are correct.

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!/2 B. (n-1)! C. (n-1)!/2 D. n!/(2n)