retagged by
20,974 views
32 votes
32 votes

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

  1. $n!$
  2. $(n-1)!$
  3. $1$
  4. $\frac{(n-1)!}{2}$
retagged by

14 Answers

2 votes
2 votes
Ques never said labelled vertices, please check that wikipedia link which is posted they proved this via taking labelled vertices,

Ans will be 1 only as there is only one hamilton graph possible as all will be isomorphic
1 votes
1 votes

Lets take an example.

If the graph has 4 vertices(a,b,c,d)  and it is complete graph. Hamiltonian graph is visiting each vertex exactly once and return back to starting vertex.

a _b_c_d_ a ...all the permutations of b,c,d is possible since it is complete graph. This permutations done in 3! ways. And b,c,d and d,c,a, all reverse pair counter twice. So, divide it by 2. Ans. Is 3!/2.

For n vertex, answer is (n-1)!/2.

 

edited by
1 votes
1 votes
This is equivalent to the garland flowers/beads problem in combinatorial analysis. The answer I think is $(n-1)! /2$
Answer:

Related questions

37 votes
37 votes
9 answers
3
1 votes
1 votes
1 answer
4
akash.dinkar12 asked Apr 8, 2019
846 views
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.