In graph theory the complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two vertices of $H$ are adjacent if and only if they are not adjacent in $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.

Formal construction

• $V\_H\; =\; V\_G$ and
• for a clique $K^n(V\_K,\; E\_K)$ of $n\; =\; |V\_G|$ vertices, $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.