GATE CS 2015 Set 2 Q28 — Graphs: Connectivity, Matching, Colouring

Let $G = (V, E)$ be a self-complementary graph on $n$ vertices, and let $\bar{G} = (V, \bar{E})$ be its complement.

By definition, a graph is self-complementary if it is isomorphic to its complement ($G \cong \bar{G}$). Isomorphic graphs must have the same number of edges, so:

The total number of edges in a complete graph $K_n$ on $n$ vertices is given by:

Substituting $|E| = |\bar{E}|$ into the equation:

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

Because $n$ and $n-1$ are consecutive integers, one of them is even and the other is odd. Thus, the factor of $4$ must divide either $n$ or $n-1$ entirely:

• If $4$ divides $n$, then $n \equiv 0 \pmod 4$.
• If $4$ divides $n-1$, then $n \equiv 1 \pmod 4$.

Hence, $n$ must be congruent to $0 \pmod 4$ or $1 \pmod 4$.

Examples:

• For $n = 4$ ($4 \equiv 0 \pmod 4$), the path graph $P_4$ is self-complementary.
• For $n = 5$ ($5 \equiv 1 \pmod 4$), the cycle graph $C_5$ is self-complementary.