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 287 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.