A cycle on n vertices is isomorphic to its complement. The value of n is 1cm .
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2014 Set 2 · Q51
Time
Your answerNumerical answer
Solution
Official answer: 5
Graph TheoryA cycle graph on vertices has edges.
The complete graph on vertices has edges.
The complement of the cycle graph, denoted , has:
If a graph is isomorphic to its complement (), they must have the same number of edges:
Since for a simple cycle graph:
For , the complement of is also a 5-cycle (), hence is self-complementary.
Try the question first, then check your work.
Examiner trap
If a graph is isomorphic to its complement, both the graph and its complement must have the same number of edges.
This Graph Theory previous year question is Q51 of the GATE CSE 2014 Set 2 paper. Find more GATE CSE PYQs on Graph Theory 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 Graph Theory 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.
Graph Theory has 21 GATE CSE PYQs across 14 papers from 2012 to 2026. 7 of them are 2-mark NAT questions like this one, and it is the only one in GATE CSE 2014 Set 2.
How GATE tests Graph TheoryIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.