Redirected
in Graph Theory retagged by
20,929 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}$
in Graph Theory retagged by
by
20.9k views

4 Comments

@muthu kumar you have considered hamiltonian cycles starting with vertex 1 only ,why not other vertex 2 also ?

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

8
8

mine is coming out n! /2

0
0

14 Answers

44 votes
44 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.
3
3

@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
2
2
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 Comments

Yup in that case answer  will  be (n-2)!/2
0
0

Hi @, @

can u pls give an example for that ?

Hamiltonian cycles starting and ending at a particular vertex v  

 

Thanks in advance

1
1

@MohanK, @K_Nishant, @Kaluti

I dont think (n-2)!/2 is correct.

Shouldn’t it be (n-1)!/2 only? As any hamiltonian cycle will contain all the vertices in the graph and a particular cycle beginning with any vertex contained within it is counted as just 1 cycle.

Can someone please confirm if I am correct?

0
0
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
1
1
Answer:

Related questions

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