GATE CSE 2019 | Question: 12

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

• A. $n!$
• B. $(n-1)!$
• C. $1$
• D. $\frac{(n-1)!}{2}$

Comments

@muthu kumar you have considered hamiltonian cycles starting with vertex 1 only ,why not other vertex 2 also ?

---

The number of different Hamiltonian cycles in

complete undirected graph on n vertices is (n − 1)! / 2

complete directed graph on n vertices is (n − 1)!

---

mine is coming out n! /2

Answer 1

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

Answer 2

Answer will be (n-1)!/2.

Answer 3

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.

 

Comments

WHAT ABOUT N=3 , why this formula fails there , because total 2 hamiltonian paths are possible , but this formula  gives only 1

Answer 4

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

Comments

Could you please explain the concept.

---

Hi, do you remember circular permutations from 12^th standard and entrance syllabus.  Check out that topic. (I tried to link a good pdf but couldn’t do it) . I think this problem reduces to the number of circular permutations on n elements. Got it?