Complement graph

In graph theory the complement or inverse of a graph ${\displaystyle G}$ is a graph ${\displaystyle H}$ on the same vertices such that two vertices of ${\displaystyle H}$ are adjacent if and only if they are not adjacent in ${\displaystyle G}$. That is to find the complement of a graph, you fill in all the missing edges to get a complete graph, and remove all the edges that were already there. It is not the set complement of the graph; only the edges are complemented.

The Petersen graph (on the left) and its complement graph (on the right).

Formal construction

Given graph ${\displaystyle G(V_{G},E_{G})}$  of vertices ${\displaystyle V_{G}}$  and edges ${\displaystyle E_{G}}$ , construct its complement graph ${\displaystyle H(V_{H},E_{H})}$  by:

• ${\displaystyle V_{H}=V_{G}}$  and
• for a clique ${\displaystyle K^{n}(V_{K},E_{K})}$  of ${\displaystyle n=|V_{G}|}$  vertices, ${\displaystyle E_{H}=E_{K}\setminus E_{G}}$ .

The complement graph is used in several graph theories and demonstrations, such as the Ramsey theory, and different reductions for proofs of NP-Completeness.