The GATE Grind

GATE 2019 CS – Question 22

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Multiple choice

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

  1. $n!$
  2. $(n-1)!$
  3. 1
  4. $\dfrac{(n-1)!}{2}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\dfrac{(n-1)!}{2}$

Explanation

A Hamiltonian cycle is a cyclic ordering of the $n$ vertices, which can be started anywhere ($n$ ways) and read in either direction (2 ways). So there are $\frac{n!}{2n}=\frac{(n-1)!}{2}$ distinct cycles.