The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
3.1k 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}$
in Graph Theory by Veteran (420k points)
edited by | 3.1k views
0
What is the answer of this question
0
A i think
0
wait guys arjun sir will post all questions shortly
0
(n-1)! / 2 in case of labelled nodes. But, nowhere mentioned in question nodes are labelled or not. What should we assume by default?
0
both C and D are correct in a final answer key

8 Answers

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

by Veteran (60.2k points)
selected by
+2

Even in its proof they have assumed vertices to be labelled, and nothing is mentioned whether vertices are labelled or not. All cycles will be isomorphic to each other and hence ans should be one. Confirmed with one of the IIT Professor as well. 

 

 

@Arjun please look into it

0
marks to all?? will the ans remains the sme.
0
we can conclude 2 ans from this.
+1
They won't give marks to all but might include C option too. Let's wait.
+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
by Junior (869 points)
+2 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 Junior (657 points)
0 votes
since nodes are not labelled, every hamilton graph will be isomorphic and hence answer will be 1.
by (15 points)
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.
by Junior (931 points)
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

by (457 points)
0 votes

Lets take an example.

If the graph has 4 vertices(a,b,c,d)  and it is complete graph. Hamiltonian graph is visiting each vertex exactly once and return back to starting vertex.

a _b_c_d_ a ...all the permutations of b,c,d is possible since it is complete graph. This permutations done in 3! ways. And b,c,d and d,c,a, all reverse pair counter twice. So, divide it by 2. Ans. Is 3!/2.

For n vertex, answer is (n-1)!/2.

 

by (11 points)
edited by
Answer:

Related questions

0 votes
1 answer
6
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,747 answers
192,248 comments
90,535 users