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

0 votes
0 votes

In complete graph,

for vertex V1=   n-1 ways to traverse

for vertex V2=  n-2 ways to traverse

for vertex V3=  n-3 ways to traverse

.

.

.

.

.

for vertex Vn=  1 way only

Hence total ways= (n-1)(n-2)(n-3)….2.1 = (n-1)!

also every path is considered twice hence  (n-1)! /2

Hence option D

0 votes
0 votes

It is same as $n$ people sitting in a circle and a person sitting left and right is same.
For $n$ people sitting in a circle the permutations are

$\frac{n!}{n}$


If left sitting right sitting doesn't matter then the permutations are

$\frac{n!}{n\times 2}$

A Hamiltonian cycle is possible for every such combination of nodes. Therefore

$\frac{(n-1)!}{2}$

edited by
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$.