Complement graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
The Petersen graph (on the left) and its complement graph (on the right).
The Petersen graph as Kneser graph KG(5,2) ...
... and its complement the Johnson graph J(5,2)

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. It is not, however, the set complement of the graph; only the edges are complemented.

Formal construction[edit]

Let G = (VE) be a simple graph and let K consist of all 2-element subsets of V. Then H = (VK \ E) is the complement of G.

Applications and examples[edit]

Several graph-theoretic concepts are related to each other via complement graphs: