in Graph Theory retagged ago by
15,939 views
27 votes
27 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 retagged ago by
by
15.9k views

4 Comments

both C and D are correct in a final answer key
0
0

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)!

7
7

11 Answers

36 votes
36 votes
Best answer

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)

selected by

4 Comments

They won't give marks to all but might include C option too. Let's wait.
2
2

@Arjun Sir, in PYQ paper 2019 on GO. When we mark option C it shows wrong . Please update it.

0
0
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
1
1
4 votes
4 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

1 comment

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

Related questions