15,939 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}$

both C and D are correct in a final answer key

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)

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.

Why it is (n-1)!. If we assume one of the initial vertex as fixed ?. If starting vertex is not fixed means it is n!.? But in question nothing mentioned above intial vertex

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

1 comment

why  A→B→C→A and A→C→B→A are the same? after all, we consider vertices in a distinctive order
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