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

can we solve this one using value of n like n = 3 ,4?

---

@halfcodeblood

For a complete graph with (n = 3) vertices substituting the value into our formula gives ({(3-1)!}{2} = {2!}{2} = 1\). This means there is exactly 1 unique Hamiltonian cycle in an undirected triangle graph

---

For a directed complete graph with (n = 3) vertices, the formula is ((n-1)!). For (n = 3), this gives ((3-1)! = 2! =) 2 unique Hamiltonian cycles.

 

Answer 1

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 2

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?

Answer 3

since nodes are not labelled, every hamilton graph will be isomorphic and hence answer will be 1.

Answer 4

Basically, say there are 3 vertices so it will be a triangle. Now, it's just a circular permutation of 3 vertices, keeping one vertex fixed, but keeping in consideration clockwise and anticlockwise permutations, we say total (n-1)!/2 permutations possible.

Answer 5

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 one thing: if you visit the vertices in the cycle in reverse order, then that's really the same cycle (because of this, the number is half of what permutations of (n-1) vertices would give you).

e.g. for vertices 1,2,3, fix "1" and you have:

123 132

but 123 reversed (321) is a rotation of (132), because 32 is 23 reversed.

There are (n-1)! permutations of the non-fixed vertices and half of those are the reverse of another, so there are (n-1)!/2 distinct Hamiltonian cycles in the complete graph of n vertices.

 

https://stackoverflow.com/questions/1387523/how-can-i-find-the-number-of-hamiltonian-cycles-in-a-complete-undirected-graph

Answer 6

The number of Hamiltonian cycles in a complete, undirected and labelled graph on n vertices is $\frac{(n-1)!}{2}$ // Option D

The number of Hamiltonian cycles in a complete, directed and labelled graph on n vertices is $(n-1)!$ 

The number of Hamiltonian cycles in a complete, unlabelled graph on n vertices is $1$ // Option C