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

@JAINchiNMay Can you show 1 eg, where it contradicts? I couldn't find any.

---

@JAINchiNMay Look at this unlabelled undirected complete graph of 6 vertices. Any cycle of length 4 you take, there's only 1 distinct because every cycle is unlabelled. 

---

Got it ….you can’t distinguish between any two cycles here

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

@Sandy Sharma

6P4= 6C4 * 4!

So after choosing 4 vertices, 4  permutation will form same cycle, i.e, v1, v2, v3, v4 after choosing , v1->v2->v3->v4->v1 is same as v2->v3->v4->v1->v2 and same for v3 and v4. So consider cyclic permutation here. Also consider clockwise and anticlockwise same.

---

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

---

@AngshukN Question says,

If vertices of G are labeled, then the

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🙌

Answer 3

Hence the answer need correction :)

Comments

For undirected:   (n-1)! / 2

For Directed:       (n-1)!
 

---

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

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.