Complement graph

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,[2] where K \ E is the relative complement of E in K. For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element ordered pairs of V in place of the set K in the formula above.

In terms of the adjacency matrix A of the graph, if Q is the adjacency matrix of the complete graph of the same number of vertices (i.e. all entries are unity except the diagonal entries which are zero), then the adjacency matrix of the complement of A is Q-A.

In the analysis of algorithms on graphs, the distinction between a graph and its complement is an important one, because a sparse graph (one with a small number of edges compared to the number of pairs of vertices) will in general not have a sparse complement, and so an algorithm that takes time proportional to the number of edges on a given graph may take a much larger amount of time if the same algorithm is run on an explicit representation of the complement graph.

In particular, it is possible to simulate either depth-first search or breadth-first search on the complement graph, in an amount of time that is linear in the size of the given graph, even when the complement graph may have a much larger size.

[8] It is also possible to use these simulations to compute other properties concerning the connectivity of the complement graph.