COMPLEMENT GRAPH

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

Contents

Formal construction

Formal construction

Given graph $G(V\_G,\; E\_G)$ of vertices $V\_G$ and edges $E\_G$, construct its 'complement graph' $H(V\_H,\; E\_H)$ by:

★ $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.