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

Question

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

Accepted Answer

(n - 1)! / 2. In a complete graph with n vertices, each Hamiltonian cycle can be represented by fixing one vertex and arranging the remaining (n-1) vertices in a cycle. Since each cycle can be traversed in two directions (clockwise and counterclockwise), we divide by 2, resulting in (n - 1)! / 2 distinct Hamiltonian cycles.

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

Solution

Related GATE Technical questions