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
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)
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
@Arjun Sir, in PYQ paper 2019 on GO. When we mark option C it shows wrong . Please update it.
Ans is (n−1)!/2.
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
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:
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.
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.