retagged by
21,006 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
since nodes are not labelled, every hamilton graph will be isomorphic and hence answer will be 1.
0 votes
0 votes
Basically, say there are 3 vertices so it will be a triangle. Now, it's just a circular permutation of 3 vertices, keeping one vertex fixed, but keeping in consideration clockwise and anticlockwise permutations, we say total (n-1)!/2 permutations possible.
0 votes
0 votes

Since the graph is complete, any permutation starting with a fixed vertex gives an (almost) unique cycle (the last vertex in the permutation will have an edge back to the first, fixed vertex. Except for one thing: if you visit the vertices in the cycle in reverse order, then that's really the same cycle (because of this, the number is half of what permutations of (n-1) vertices would give you).

e.g. for vertices 1,2,3, fix "1" and you have:

123 132

but 123 reversed (321) is a rotation of (132), because 32 is 23 reversed.

There are (n-1)! permutations of the non-fixed vertices and half of those are the reverse of another, so there are (n-1)!/2 distinct Hamiltonian cycles in the complete graph of n vertices.

 

https://stackoverflow.com/questions/1387523/how-can-i-find-the-number-of-hamiltonian-cycles-in-a-complete-undirected-graph

0 votes
0 votes

The number of Hamiltonian cycles in a complete, undirected and labelled graph on n vertices is $\frac{(n-1)!}{2}$ // Option D

The number of Hamiltonian cycles in a complete, directed and labelled graph on n vertices is $(n-1)!$ 

The number of Hamiltonian cycles in a complete, unlabelled graph on n vertices is $1$ // Option C

Answer:

Related questions

37 votes
37 votes
9 answers
3
1 votes
1 votes
1 answer
4
akash.dinkar12 asked Apr 8, 2019
849 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$.