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

  1. $n!$
  2. $(n-1)!$
  3. $1$
  4. $\frac{(n-1)!}{2}$
in Graph Theory by Veteran
edited by | 5.3k views
What is the answer of this question
A i think
wait guys arjun sir will post all questions shortly
(n-1)! / 2 in case of labelled nodes. But, nowhere mentioned in question nodes are labelled or not. What should we assume by default?
both C and D are correct in a final answer key

9 Answers

+16 votes
Best answer

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

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)

by Veteran
selected by

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

marks to all?? will the ans remains the sme.
we can conclude 2 ans from this.
They won't give marks to all but might include C option too. Let's wait.

@Arjun Sir, in PYQ paper 2019 on GO. When we mark option C it shows wrong . Please update 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
by Junior
+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

by Junior
why  A→B→C→A and A→C→B→A are the same? after all, we consider vertices in a distinctive order
0 votes
since nodes are not labelled, every hamilton graph will be isomorphic and hence answer will be 1.
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.
by Active
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.

by Junior
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.


edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,223 questions
59,816 answers
118,088 users