3.1k views

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}$

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

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)

by Veteran (60k points)
selected by
+2

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.

0
marks to all?? will the ans remains the sme.
0
we can conclude 2 ans from this.
+1
They won't give marks to all but might include C option too. Let's wait.
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 (837 points)
+1 vote

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 (627 points)
since nodes are not labelled, every hamilton graph will be isomorphic and hence answer will be 1.
by (15 points)
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 Junior (883 points)

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

by (447 points)

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.

by (11 points)
edited by

1
2
+1 vote