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
GATE CSE 2012 · Q38
Time
Select one answerSingle correct
Solution
Official answer: See verified solution
CombinatoricsTo find the number of distinct cycles of length 4 in a complete labeled graph :
Choose 4 vertices out of the 6 vertices:
The number of distinct undirected cycles that can be formed using a specific set of 4 labeled vertices is:
Therefore, the total number of distinct 4-cycles in is:
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.
Examiner trap
First choose 4 vertices from the 6 available vertices, then calculate the number of distinct undirected cycles of length 4 formed on those vertices: .
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
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.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
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 CombinatoricsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.