Complement graph
From Wikipedia, the free encyclopedia
The Petersen graph (on the left) and its complement graph (on the right).
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.
[edit] Formal construction
Given graph G(VG,EG) of vertices VG and edges EG, construct its complement graph H(VH,EH) by:
- VH = VG and
- for a clique Kn(VK,EK) of n = | VG | vertices,
.
The complement graph is used in several graph theories and demonstrations, such as the Ramsey theory, and different reductions for proofs of NP-Completeness.
