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 (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.