Complement Graphs

Definition: For a graph $G = (V(G), E(G))$, the Complement of $G$ denoted $\bar{G}$ (or $G^c$) is the graph with vertex set $V(G)$ and edge set $[V(G)]^2 \backslash E(G)$, that is $\bar{G} = (V(G), [V(G)]^2 \backslash E(G))$.

Essentially, if a graph $G$ is on n-vertices then the complement $\bar{G}$ is the complete graph $K_n$ with all of the edges in $G$ deleted. We can see this very clearly in the following example showing both the graph $G$ and its complement:

Since the vertex set for $\bar{G}$ is the same as $G$, the number of vertices in the complement of $G$ is the same as that in $G$, that is:

(1)

\begin{align} \quad \mid V(\bar{G}) \mid = \mid \: V(G) \: \mid \end{align}

However, the number of edges in the complement of $G$ can be calculated differently. Recall that the number of edges in a complete graph is $\frac{n(n-1)}{2}$. Hence it follows that:

(2)

\begin{align} \quad \mid E(\bar{G}) \mid = \frac{n(n-1)}{2} - \mid E(G) \mid \end{align}