GATE CS 2019 Q12 — Graphs: Connectivity, Matching, Colouring

To find the number of different Hamiltonian cycles in an undirected complete graph $G = K_n$ on $n$ vertices (where $n > 2$):

1. General Formula Derivation

• A Hamiltonian cycle visits every vertex of the graph exactly once and returns to the starting vertex.
• Since the graph is complete ($K_n$), every vertex is connected to every other vertex.
• Fixing a starting vertex to avoid cyclic shifts, there are $(n-1)!$ ways to arrange the remaining $n-1$ vertices in a sequence.
• Because the graph is undirected, a cycle traversed in the clockwise direction is identical to the same cycle traversed in the counter-clockwise direction (e.g., $v_1 \to v_2 \to v_3 \to v_1$ is the same as $v_1 \to v_3 \to v_2 \to v_1$).
• Therefore, we divide the total permutations by $2$ to account for this reversal symmetry: $$\text{Number of Hamiltonian cycles} = \frac{(n-1)!}{2}$$

This matches Option D.

2. Special Case ($n = 3$)

• The problem states $n > 2$. If we consider the case where $n = 3$: $$\frac{(3-1)!}{2} = \frac{2!}{2} = 1$$
• Thus, for $n = 3$, the number of different Hamiltonian cycles is exactly $1$.

This matches Option C.

Since both interpretations are valid, both Option C and Option D are correct.