GATE 2019 CS – Question 22
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
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.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2019 CS Q56
- GATE 2018 CS Q28
- GATE 2018 CS Q53
- GATE 2015 CS (CS1) Q44
- GATE 2017 CS (CS1) Q30
- GATE 2014 CS (CS1) Q61
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →