Complement graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 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:

References[edit]