GATE CS 2015 Set 2 Q.38 (CS Q.28): Graph Theory

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is

A multiple of 4

Even

Odd

Congruent to 0 mod 4, or, 1 mod 4

Official answer and solution

Solution

Use the edge-counting argument for self-complementary graphs.

A graph $G = (V, E)$ on $n$ vertices is self-complementary if $G \cong \overline{G}$ .

The complete graph $K_n$ has total edges:

|E(K_n)| = \binom{n}{2} = \frac{n(n - 1)}{2}.

Because $G$ and $\overline{G}$ partition the edges of $K_n$ and have identical edge counts due to isomorphism:

|E(G)| + |E(\overline{G})| = 2 |E(G)| = \frac{n(n - 1)}{2} \implies |E(G)| = \frac{n(n - 1)}{4}.

Since the number of edges $|E(G)|$ must be an integer, $n(n - 1)$ must be divisible by 4:

n(n - 1) \equiv 0 \pmod 4.

Hence, $n \equiv 0 \pmod 4$ or $n \equiv 1 \pmod 4$ (option D).

Final answer

Common trap

Assuming $n$ must simply be even or a multiple of 4, overlooking odd values such as $n = 5$ (which forms a self-complementary 5-cycle $C_5$ ).

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

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