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

Applications

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

References

• Bondy, John Adrian; Murthy, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7, pages 6 and 29.
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.