Complement Graph

Definition

Complement Graph

Let $G=(V,E)$ be a finite simple undirected graph. The complement graph of $G$ is the graph

$$\overline{G}=(V,\overline{E}),\overline{E}=\left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E,$$

where $\left(\genfrac{}{}{0ex}{}{V}{2}\right)$ is the set of all unordered pairs of distinct vertices in $V$. Thus, $G$ and $\overline{G}$ have the same vertices, and for every distinct $u,v\in V$,

$$\{u,v\}\in \overline{E}⟺\{u,v\}\notin E.$$

Complementation therefore replaces every edge by a non-edge and every non-edge between distinct vertices by an edge.

Complementing Twice

Complementation is an involution:

$$\overline{\overline{G}}=G.$$

Each unordered pair has its adjacency status reversed twice, so the original graph is recovered.

Edge Count

If $|V|=n$, then $G$ and its complement divide all possible edges between them:

$$E\cap \overline{E}=\varnothing ,E\cup \overline{E}=\left(\genfrac{}{}{0ex}{}{V}{2}\right),|\overline{E}|=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-|E|.$$

Cliques and Independent Sets

A clique and an independent set exchange roles under complementation. For every $S\subseteq V$,

$$\begin{array}{rl}S\text{ is a clique in }G& ⟺S\text{ is independent in }\overline{G},\\ S\text{ is independent in }G& ⟺S\text{ is a clique in }\overline{G}.\end{array}$$

This correspondence is the mechanism behind the Independent Set to Clique reduction.