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
Let G = (V, E) be a simple graph and let K consists of all 2-element subsets of V. Then H = (V, K \ E) is the complement of 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.