GATE CSE 2012 | Question: 38

Question

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

• A. $15$
• B. $30$
• C. $90$
• D. $360$

Comments

correct answer is 45

---

don't try to memorize anything for gate

 

---

1. Select the Vertices

First, choose 4 vertices out of the 6 available vertices to form the cycle:

$$\binom{6}{4} = \frac{6 \times 5}{2 \times 1} = 15$$

2. Arrange the Vertices into a Cycle

For any chosen set of $k$ distinct vertices, the number of distinct cycles of length $k$ in an undirected graph is given by:

$$\frac{(k - 1)!}{2}$$

For $k = 4$:

$$\frac{(4 - 1)!}{2} = \frac{3!}{2} = \frac{6}{2} = 3$$

3. Total Number of Cycles

Multiply the number of ways to select 4 vertices by the number of distinct cycles formed by those 4 vertices:

$$\text{Total cycles} = 15 \times 3 = 45$$

The number of distinct cycles of length 4 in $G$ is 45.

Answer 1

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.

Comments

The question doesn’t say whether the vertices are labelled or unlabelled

---

@AngshukN Question says,

If vertices of G are labeled, then the

---

got it

Answer 2

There can be total ⁶C₄ ways to pick 4 vertices from 6. The value of ⁶C₄ 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.

Comments

This explanation is perfect: simple and understandable.

---

Perfect answer.

---

great🙌

---

it's somewhere related to circular arrangement...

Answer 3

Hence the answer need correction :)

Comments

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?

---

Very nice doubt cleared but if they don't mention about distinct cycles the concept of circular permutation is used.......

---

thnks a lot

 

Answer 4

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.

Answer 5

Answer would be ⁶C₄ * 4! /(4*2) =45

Explanation:

Number of ways to choose 4 vertices = ⁶C₄
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)

Comments

Since graph is undirected ,why we are considering directions in the cycle ?

---

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.

---

Ohh yes!

Thanks

Answer 6

From 6 vertices we select 4 vertices in ⁶C₄ = 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.

Comments

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

---

if cycles are distinct then no need to divide by 2 here in circular permutation

---

vertices of G are labeled explain this line

---

what dose it mean that every cycle is 2-regular?