6.1k 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
retagged | 6.1k views
0
Option need correction.
0

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.
edited
–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?
+1
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 :)

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.

+1
This explanation is perfect: simple and understandable.

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)

edited
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

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.

+1

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?
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
edited
+2
Calculation mistake :)
+1
If labels are a-b-c-d then please give the 3 cycles.