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.

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 Ramsey theory, and in certain reductions for proofs of NP-Completeness.

File:GraphComplement 701.gif Original Complement Complete

(Simple version) If you want to get complement of a graph simply redraw the graph without any edges then connect all the points that weren't connected in the original.