Complement graph

In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices are adjacent (connected) in H 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.

The complement of the graph is not the set complement of the graph: only the edges are complemented.

Definitions

Let G = (V, E) be a simple undirected graph and let P consist of all pairs of distinct vertices in V. Then the simple undirected graph H = (V, P \ E) is the complement of G, where P \ E is the relative complement of E in P.

Let G = (V, A) be a simple directed graph and let O consist of all ordered pairs of distinct vertices in V. Then the simple directed graph H = (V, O \ A) is the complement of G.

Let G be a simple undirected / directed graph, let K be the complete simple undirected / directed graph on the same number of vertices (i.e., all entries are unity except the diagonal entries which are zero), let

A

(

G

)

{\displaystyle \mathbb {A} (G)}

and

A

(

K

)

{\displaystyle \mathbb {A} (K)}

respectively be the adjacency matrices of G and K. Then the adjacency matrix of the complement H of G is:

A

(

H

)

=

A

(

K

)

−

A

(

G

)

{\displaystyle \mathbb {A} (H)=\mathbb {A} (K)-\mathbb {A} (G)}

.

The complement is not defined for multigraphs.

For graphs that allow self-loops (but not multiple adjacencies), the complement of a graph G may be defined by adding a self-loop to every vertex that does not have one in G, removing its self-loop from every vertex that has one in G, and otherwise using the same formula as above. However, this operation is different from the one for simple graphs, since applying it to a graph with no self-loop results in a graph with self-loops on all vertices.

Applications and examples

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

The complement of an edgeless graph is a complete graph, and vice versa.

Any induced subgraph of the complement graph of a graph G is the complement of the corresponding induced subgraph in G.

An independent set in a graph is a clique in the complement graph, and vice versa. This is a special case of the previous two properties, as an independent set is an edgeless induced subgraph and a clique is a complete induced subgraph.

The automorphism group of a graph is the automorphism group of its complement.