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
complete undirected graph on n vertices is (n − 1)! / 2
complete directed graph on n vertices is (n − 1)!
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)
@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