Complement graph

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

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

Applications and examples

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

• The vertices of the Kneser graph KG(n,k) are the k-subsets of an n-set, and the edges are between disjoint sets. The complement is the Johnson graph J(n,k), where the edges are between intersecting sets.
• The complement of an edgeless graph is a complete graph and vice versa.
• An independent set in a graph is a clique in the complement graph and vice versa.
• The complement of every triangle-free graph is a claw-free graph, although the reverse is not true.
• A self-complementary graph is a graph that is isomorphic to its own complement. Examples include the four-vertex path graph and five-vertex cycle graph.
• Cographs are defined as the graphs that can be built up from disjoint union and complementation operations, and form a self-complementary family of graphs: the complement of any cograph is another (possibly different) cograph.