GateAI
Graph Theory

GATE CSE 2014 Set 2 · Q51

NAT2 marksEasy

Time

A cycle on nn vertices is isomorphic to its complement. The value of nn is ‾ \underline{\hspace{1cm}} .

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 5

Graph Theory

A cycle graph CnC_n on nn vertices has nn edges.

The complete graph KnK_n on nn vertices has n(n−1)2\frac{n(n-1)}{2} edges.

The complement of the cycle graph, denoted Cn‾\overline{C_n}, has:

∣E(Cn‾)∣=n(n−1)2−n=n(n−3)2|E(\overline{C_n})| = \frac{n(n-1)}{2} - n = \frac{n(n-3)}{2}

If a graph is isomorphic to its complement (Cn≅Cn‾C_n \cong \overline{C_n}), they must have the same number of edges:

n=n(n−3)2n = \frac{n(n-3)}{2}

Since n≥3n \ge 3 for a simple cycle graph:

2=n−3  ⟹  n=52 = n - 3 \implies n = 5

For n=5n = 5, the complement of C5C_5 is also a 5-cycle (C5C_5), hence C5C_5 is self-complementary.

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

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

Graph Theory in GATE CSE

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 Theory

More from GATE CSE 2014 Set 2

Share this solution

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

GateAI solution cardGATE CSE 2014 Set 2 · Q51 · NAT

A cycle on n vertices is isomorphic to its complement. The value of n is 1cm .

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.