The Gateway to Computer Science Excellence
+78 votes
13.5k views

Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to

  1. $15$
  2. $30$
  3. $90$
  4. $360$
in Graph Theory by
retagged by | 13.5k views
0
Option need correction.
0
yes 45 is the answer
0
Here direction of cycles is not important. right??
0
Yes. It is undirected graph.
+1

$undirected\ \&\ labelled=\binom{6}{4}\times \dfrac{3!}{2}\ =45$

$undirected\ \&\ unlabelled=1\times 1=1$


@Lakshman Patel RJIT @Verma Ashish

$directed\ \&\ labelled=\binom{6}{4}\times 3!\ =90\ ?$

$directed\ \&\ unlabelled=1\times 3!=6\ ?$

+1

@Kushagra गुप्ता  directed and unlabeled- i am getting only one

+1

@Verma Ashish

Yes, you are right. It will be $1\times 1=1$ only. Thanks

8 Answers

+142 votes
Best answer
From $6$ vertices we can select $4$ distinct vertices in $^{6}C_{4} = 15$ ways.
Now, with $4$ vertices, we can form only $3$ distinct cycles. [See below]
So, total no. of distinct cycles of length $4 = 15\times 3 = 45.$

No. of cyclic permutations of n objects $=\left(n-1\right)!$ and for $n = 4,$ we get $3! = 6$ ways. But number of distinct cycles in a graph is exactly half the number of cyclic permutations as there is no left/right ordering in a graph. For example $a - b - c - d$ and $a - d - c - b$ are different permutations but in a graph they form the same cycle.

Since, $45$ was not in the choice, marks were given to all in GATE.
by
edited by
–3
I'm trying to understand this, any help will be great. I understand that it is circular permutation. But I'm unable to understand the flaw in the following solution.

Why can't it be 1x for the first vertex in the cycle, followed by 5x4x3 possibilities for the other three vertices and whole divided by 2 for the direction?

That is $1*5*4*3/2 = 30$
+8
In case of unlabelled vertices it should be 1 right ?
+7
overall 1,yes right.
0
Very well explained. .
0
What is the answer if question does not say distinct?
0
Then it will be treated as unlabelled graph .
0
What will be the answer then?If the question says:-

Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of cycles of length 4 in G is equal to
0
45 not given in the option so what will be the ans????
+3
@Bikram Sir, We can also solve like:-

A --- B --- C --- D----A

here A, B, C, D are the blank spaces, where first A and Last A is the blank which will be filled by same vertices:-

A --- B --- C --- D---A

6 X   5  X  4 X 3 X 1

is the total permutation and since clock wise and anti clock wise rotations are same, so div by 2.

we get 360/2 = 180.

Why this is wrong?
+11
Hello shubhanshu

Your approach is correct but you are forgetting it to divide by 4.

let suppose you choose acbda  now by your method you're counting it 4 times like dacbd,cbdac,bdacb. so divide 180 by 4 and hence 45.
+1
Hello rahul

As vertices are leveled so by default cycle would be distinct , even if they don't mention distinct , cycle would be suppose to be distinct when we leveled vertices.

if graph is unleveled then with 4 vertices we can make only one cycle so here answer would be 1.
0
@rupendra So overall answer will be 6C2x1=15 or only 1? Because vertices are unlabelled and any 4 selection of vertices will not matter. Please clarify this one.
+1
Hello minipanda

First you tell me number of ways to select 4 Apples from 6 identical Apples.
+2
@rupendra It's 1. Okay. So here unlabelled vertices are similar to identical apples ! And ways of choosing 4 from 6 is 1. So 1x1 is 1 :P
Thank you :)
0
I understood the answer.

What is wrong in this :

6P4 instead bof 6C4 as order is important.

Then , 6P4/2 as anticlockwise and clockwise sequence are same.

V1->v2->v3->v4 = v4->v3->v2->v1

This will result to 30.

What is wrong in this approach?
+69 votes

There can be total 6C4 ways to pick 4 vertices from 6. The value of 6C4 is 15.

Note that the given graph is complete so any 4 vertices can form a cycle.

There can be 6 different cycle with 4 vertices. For example, consider 4 vertices as a, b, c and d. The three distinct cycles are

cycles should be like this
(a, b, c, d,a)
(a, b, d, c,a)
(a, c, b, d,a)
(a, c, d, b,a)
(a, d, b, c,a)
(a, d, c, b,a)

and

(a, b, c, d,a) and (a, d, c, b,a)
(a, b, d, c,a) and (a, c, d, b,a)
(a, c, b, d,a) and (a, d, b, c,a)
are same cycles.

So total number of distinct cycles is (15*3) = 45.

The answer is 45.

by
+3
This explanation is perfect: simple and understandable.
+17 votes

Hence the answer need correction :)

by
+1
Nice Answer 👌
0
nice explaination . example make it visible . thnxx bro
+7

For undirected graph 

 complete graph $K_{4}$ number of distinct cycles $=\frac{3!}{2}=3$ (Here direction does not matter)

For directed graph 

 complete graph $K_{4}$ number of distinct cycles $=3!=6$ (Here direction  matter)

+1

@Lakshman Patel RJIT cycles of size 4 

0

For undirected:   (n-1)! / 2

For Directed:       (n-1)!
 

0
can you tell me how you come up with (n-1)!/2 for undirected.  i mean for first vertices we can select it by 4 ways then 3 ways and then 2 ways which is 4*3*2 and if the length of cycle changes does it affect the formula?
+14 votes

Answer would be 6C4 * 4! /(4*2) =45

Explanation:

Number of ways to choose 4 vertices = 6C4
Total number of cycles from a particular set of 4 vertices = 4!/(4*2) (since the same cycle can start from different vertices and go in both directions)

by
edited by
0
Since graph is undirected ,why we are considering directions in the cycle ?
+2
Consider two representations (abcda or adcba.) of the same cycle. To  count such cycle only once I divide the total number of cycles by 2.
0
Ohh yes!

Thanks
+9 votes

From 6 vertices we select 4 vertices in 6C4 = 15 ways.
Now, with these 4 vertices, we can form only 3 distinct cycles.

How ? Since, all 4 vertices have adjacent edge to other 3 choosen vertices, i.e. total 6 edges. Now every cycle is 2-regular. Therefore, every vertice is adjacent to 2 other vertices. So, for first vertex, we have 3 choices to choose 2 adjacent vertices out of 3 vertices. Now, we have drawn 2 lines of cycle and selected 3 vertices out of 4. For last, we have no choice, since first vertex already rejected it to be its adjacent. so, it will join to other vertices.

Hence 15*3=45 is the answer.

by
+1
what would be the answer???

1- if cycles are distict

2- if cycles are not distict

​​​​​​all details are same as in above question given....​please explain in detail...
0
if cycles are distinct then no need to divide by 2 here in circular permutation
0
vertices of G are labeled explain this line
0
what dose it mean that every cycle is 2-regular?
+8 votes
lets discuss for general graph if $k_{n}$ is complete graph then to select cycle of m length we require $\binom{n}{m}$ after selecting each cycle we to also arrange them in different way so it takes (m-1)!/2 , because in order to arrange in cycle , so total cycle will be $\binom{n}{m}$(m-1)!/2

therefore for 6 vertices we required no of cycle of length 4 = (6c4)(4-1)!/2=45
by
edited by
+2
Calculation mistake :)
+1
If labels are a-b-c-d then please give the 3 cycles.
+6 votes

This question asks for Hamiltonian cycles.

The corresponding formulae for complete graphs are:-

  • undirected: $(n-1)!/2$
     
  • directed: $(n-1)!$
     
  • The above two are applicable only when graph is labelled. If unlabelled, then we can't distinguish between cycles. Let all the nodes be labelled A (it is equivalent to them being unlabelled)
    A —> A —> A —> A
    A —> A —> A —> A
    Do you see any difference? Me neither :P

    Hence, when the graph is unlabelled, hamiltonian cycles possible are $1$ — no matter the type of edges (directed or undirected)

 


The question pertains to the first formula.

Ways to select 4 vertices out of 6 = ${^6C_4}=15$ (In a complete graph, each 4 vertices will give a 4 edged cycle)

Hamiltonian cycles possible on each such 4 vertices = $(4-1)!/2=3$

So, total = $15*3=45$

(Answer)


What if the graph was unlabelled?

By the third formula here, the answer would be 1. We don't care if the edges are directed or undirected; if the graph is unlabelled, hamiltonian cycles possible will always be 1.


What if the edges were directed?

By the second formula here, it'll be $15*(4-1)!$

Which is equal to $90$

 

Sources: https://en.wikipedia.org/wiki/Hamiltonian_path

And to understand from where do $(n-1)!/2$ and $(n-1)!$ come from, give this a read. Won't take more than 5 minutes.

by
0 votes

Answer : 45

Total no. of cycles of length 'k' in a complete graph of n vertices = [ nCk ]*(k-1)!/2

so, 6C4 * (4-1)!/2

=15*3 = 45

by
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
52,345 questions
60,470 answers
201,796 comments
95,272 users