The Gateway to Computer Science Excellence

+78 votes

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

- $15$
- $30$
- $90$
- $360$

+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\ ?$

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

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.

–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$

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$

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

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

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

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.

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.

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.

+69 votes

There can be total ^{6}C_{4} ways to pick 4 vertices from 6. The value of ^{6}C_{4} 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.**

+17 votes

+14 votes

Answer would be ^{6}C_{4} * 4! /(4*2) =45

Explanation:

Number of ways to choose 4 vertices = ^{6}C_{4}

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)

+9 votes

From 6 vertices we select 4 vertices in ^{6}C_{4} = 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.

+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

therefore for 6 vertices we required no of cycle of length 4 = (6c4)(4-1)!/2=45

+6 votes

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)

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.

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.

52,345 questions

60,470 answers

201,796 comments

95,272 users