GateAI
Combinatorics

GATE CSE 2012 · Q38

MCQ2 marksMedium

Time

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

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: See verified solution

Combinatorics

To find the number of distinct cycles of length 4 in a complete labeled graph K6K_6:

  1. Choose 4 vertices out of the 6 vertices:

    (64)=15\binom{6}{4} = 15
  2. The number of distinct undirected cycles that can be formed using a specific set of 4 labeled vertices is:

    (4−1)!2=3!2=62=3\frac{(4 - 1)!}{2} = \frac{3!}{2} = \frac{6}{2} = 3
  3. Therefore, the total number of distinct 4-cycles in K6K_6 is:

    15×3=4515 \times 3 = 45

Since 45 was not present among the given options (15, 30, 90, 360), marks were awarded to all candidates (Marks to All in the official key).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Combinatorics previous year question is Q38 of the GATE CSE 2012 paper. Find more GATE CSE PYQs on Combinatorics in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Combinatorics PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Combinatorics in GATE CSE

Combinatorics has 19 GATE CSE PYQs across 15 papers from 2012 to 2025. 5 of them are 2-mark MCQs like this one, and GATE CSE 2012 has 2.

How GATE tests Combinatorics

More from GATE CSE 2012

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2012 · Q38 · MCQ

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

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.