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, and remove all the edges that were already there. It is not the set complement of the graph; only the edges are complemented.

File:GraphComplement 701.gif

Original graph (red), its complement (blue), and the union of both, thta gives a complete

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.