Let 𝐺 be an undirected complete graph on 𝑛 vertices, where 𝑛 > 2. Then, the…
2019
Let 𝐺 be an undirected complete graph on 𝑛 vertices, where 𝑛 > 2. Then, the number of different Hamiltonian cycles in 𝐺 is equal to
Answer: D. \(\frac {(𝑛−1)!} {2}\) — Answer: (n−1)!/2 Step 1: Remove cyclic symmetry by fixing one vertex as the start. The remaining (n−1) vertices can be arranged in (n−1)! orders, giving all…
- A.
𝑛!
- B.
(𝑛 − 1)!
- C.
1
- D.
\(\frac {(𝑛−1)!} {2}\)
Attempted by 279 students.
Show answer & explanation
Correct answer: D
Answer: (n−1)!/2
Step 1: Remove cyclic symmetry by fixing one vertex as the start. The remaining (n−1) vertices can be arranged in (n−1)! orders, giving all possible cyclic orderings up to rotation.
Step 2: In an undirected graph, each cyclic ordering and its reverse correspond to the same Hamiltonian cycle, so divide by 2 to account for this reflection symmetry.
Conclusion: The number of distinct Hamiltonian cycles in the undirected complete graph on n>2 vertices is (n−1)!/2.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2