The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+48 votes
6.8k 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$
asked in Graph Theory by Boss (18.1k points)
retagged by | 6.8k views
0
Option need correction.
0
yes 45 is the answer

5 Answers

+95 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.
answered by Boss (18.1k points)
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$
+2
In case of unlabelled vertices it should be 1 right ?
+2
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????
0
@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?
+2
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.
0
Hello minipanda

First you tell me number of ways to select 4 Apples from 6 identical Apples.
0
@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?
+27 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.

answered by Loyal (6.7k points)
+1
This explanation is perfect: simple and understandable.
+12 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)

answered by Loyal (5.7k points)
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.

answered by (173 points)
+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?
+5 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
answered by Active (4.9k points)
edited by
+2
Calculation mistake :)
+1
If labels are a-b-c-d then please give the 3 cycles.


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

39,645 questions
46,730 answers
140,391 comments
58,091 users