GATE CS 2014 Set 2 Q51 — Graphs: Connectivity, Matching, Colouring

For a graph $G$ to be isomorphic to its complement $\overline{G}$, they must have the same number of vertices and the same number of edges.

Let $C_n$ be a cycle on $n$ vertices (where $n \ge 3$).

• The number of vertices in $C_n$ is $n$.
• The number of edges in $C_n$ is $n$.

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

The number of edges in the complement graph $\overline{C_n}$ is:

Since $C_n$ is isomorphic to $\overline{C_n}$, their edge counts must be equal:

Since $n \ge 3$ for a cycle, we divide by $n$:

Verification:
For $n = 5$, the cycle $C_5$ is a 2-regular graph. Its complement $\overline{C_5}$ is also a 2-regular connected graph on 5 vertices, which is indeed a 5-cycle. Thus, $C_5 \cong \overline{C_5}$.