GATE CS Mastery
Cheat sheets

GATE CS 2012 · Engineering Mathematics

Question 38

MCQPrinted as CS Q.382 marksNo negative markingMedium (estimate)Marks to all

Question

Let GG be a complete undirected graph on 6 vertices. If vertices of GG are labeled, then the number of distinct cycles of length 4 in GG is equal to

Choose one option
Official answer and solution
Official answer
Marks to all
From
Official GATE 2012 answer key
Why the marks went to every candidate

Official GATE answer key awarded Marks to All for this question.

Solution

Count the number of distinct cycles of length 4 in a complete graph on 6 labeled vertices.

  1. In complete graph K6K_6, an undirected cycle of length 4 is determined by:
  • Selecting 4 vertices out of 6:
(64)=6×52×1=15\binom{6}{4} = \frac{6 \times 5}{2 \times 1} = 15
  • The number of distinct undirected cycles that can be formed using 4 given vertices is:
(4−1)!2=3!2=62=3\frac{(4 - 1)!}{2} = \frac{3!}{2} = \frac{6}{2} = 3
  1. Multiplying these values gives the total number of distinct 4-cycles:
Total 4-cycles=15×3=45\text{Total 4-cycles} = 15 \times 3 = 45
  1. The value 45 was not present among the four printed options (15, 30, 90, 360). Due to this printing discrepancy, GATE awarded Marks to All to all candidates.
Final answer

Marks to All (Mathematically 45 distinct 4-cycles exist; Marks to All awarded due to missing option).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2012 Computer Science and Information Technology (CS)
Question
38 of 65, printed as CS Q.38
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.