recategorized by
279 views

1 Answer

Best answer
7 votes
7 votes
Since the graph is complete, any permutation starting with a fixed vertex gives an (almost) unique cycle (the last vertex in the permutation will have an edge back to the first, fixed vertex),  except for the fact that if we visit the vertices of the cycle in reverse order, it is really the same cycle. Thus the number of cycles is half of the number of permutations of $(n-1).$

There are $(n-1)!$ permutations of the non-fixed vertices, and half of those are the reverse of another, so there are $\dfrac{(n-1)!}{2}$ distinct Hamiltonian cycles in the complete graph of $n$ vertices.
$$\left(\textbf{OR}\right)$$
The number of ways to arrange $n$ distinct objects along a fixed circle is $(n-1)!.$ If clock-wise and anti-clockwise cycle is same then we divide total permutations with $2$. For example two cycles $123$ and $321$ both are same because they are reverse of each other.

For all $n\geq 3$, the number of distinct Hamilton Cycles in a complete graph $K_{n}$ is $\dfrac{(n-1)!}{2}.$

The number of Hamiltonian cycles in $K_{8} = \dfrac{(8-1)!}{2}=\dfrac{7!}{2} = 2520$.

So, the correct answer is $2520$.
selected by
Answer:

Related questions

3 votes
3 votes
1 answer
1
gatecse asked Sep 14, 2020
207 views
Which of the following graphs has a Hamiltonian path?$S_1:$$S_2:$$S_1$ only$S_2$ onlyBoth $S_1$ and $S_2$Neither $S_1$ nor $S_2$
1 votes
1 votes
1 answer
2
gatecse asked Sep 14, 2020
195 views
If $G$ is a simple graph with $16$ edges and $\overline{G}$ has $12$ edges, how many vertices does the complement graph $\overline{G}$ have?
4 votes
4 votes
1 answer
3
gatecse asked Sep 14, 2020
318 views
The number of possible connected simple graphs with $3$ labelled vertices is ________
1 votes
1 votes
1 answer
4
gatecse asked Sep 14, 2020
127 views
Suppose a simple graph has $45$ edges, $5$ vertices of degree $6$, and all others of degree $5$. How many vertices does the graph have?