The Gateway to Computer Science Excellence

+12 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

- $n!$
- $(n-1)!$
- $1$
- $\frac{(n-1)!}{2}$

+16 votes

Best answer

The number of different Hamiltonian cycles in a complete undirected **labeled **graph on $n$ vertices is $(n − 1)! / 2$.

Ref : https://en.wikipedia.org/wiki/Hamiltonian_path

If the graph is unlabeled number of different Hamiltonian cycles become $1.$

Since the question does not mention whether the graph is labeled or not, answer can be either (C) or (D).

Official answer key is (D) or (C)

+3

Even in its proof they have assumed vertices to be labelled, and nothing is mentioned whether vertices are labelled or not. All cycles will be isomorphic to each other and hence ans should be one. Confirmed with one of the IIT Professor as well.

@Arjun please look into it

+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

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

+2 votes

From any vertex we have n−1 edges to choose from first vertex, n−2 edges to choose from second vertex, n−3 to choose from the third and so on. These being independent choices, we get (n−1)! possible number of choices.

Each Hamiltonian circuit has been counted twice (in reverse direction of each other like these: A→B→C→A and A→C→B→A).

**Number of distinct not edge disjoint Hamiltonian circuits in complete graph Kn is (n−1)!/2**

0 votes

0 votes

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.

0 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 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.

0 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.

52,223 questions

59,816 answers

201,021 comments

118,088 users