GATE CS 2019 Q.22 (CS Q.12): Graph Theory

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

$n!$

$(n - 1)!$

$1$

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

Official answer and solution

Accepted answers: C, or D
From: Official GATE 2019 answer key

Note on this question

Official answer key accepted both C and D. The standard theoretical formula for undirected Hamiltonian cycles in K_n is (n - 1)! / 2 (Option D), which equals 1 for n = 3 (Option C).

Solution

Calculate the number of undirected Hamiltonian cycles in a complete graph K_n.

In a complete undirected graph $K_n$ with $n > 2$ vertices:

A Hamiltonian cycle visits every vertex exactly once and returns to the start vertex.
Starting at an arbitrary fixed vertex, the remaining $n - 1$ vertices can be visited in $(n - 1)!$ cyclic orders.
Because the graph is undirected, traversing the cycle in the clockwise direction and the counter-clockwise direction traverses the exact same set of edges.
Dividing by 2 for the direction of traversal gives:

\text{Number of undirected Hamiltonian cycles} = \frac{(n - 1)!}{2}

For $n = 3$ , $\frac{(3 - 1)!}{2} = \frac{2}{2} = 1$ .
Due to ambiguous wording in the question (whether a general formula or a specific minimum case $n=3$ was sought), the official GATE answer key accepted both Option C (1) and Option D ( $\frac{(n - 1)!}{2}$ ).

Final answer

Common trap

Forgetting to divide by 2 for undirected cycles, which yields directed cycles (n - 1)!.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 22 of 65, printed as CS Q.12
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source