retagged by
20,981 views
32 votes
32 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}$
retagged by

14 Answers

Best answer
44 votes
44 votes

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
23 votes
23 votes

Circular Permutations: The number of ways to arrange n distinct objects along a fixed circle is (n-1)! . If clock-wise and anti-clockwise cycle is same then we divide total permutations with 2. for example two cycles 123 and 321 both are same because they are reverse of each other.

For all n≥3, the number of distinct Hamilton Cycles in a complete graph $K_{n}$ is $\frac{(n-1)!}{2}$

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

Answer:

Related questions

37 votes
37 votes
9 answers
3
1 votes
1 votes
1 answer
4
akash.dinkar12 asked Apr 8, 2019
846 views
Show that if the edge set of the graph $G(V,E)$ with $n$ nodes can be partitioned into $2$ trees, then there is at least one vertex of degree less than $4$ in $G$.