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
- A.
π!
- B.
(π β 1)!
- C.
1
- D.
\(\frac {(πβ1)!} {2}\)
Attempted by 208 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.