Complement (graph theory)

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.

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, 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.

The complement is not defined for multigraphs. In graphs that allow self-loops (but not multiple adjacencies) the complement of G may be defined by adding a self-loop to every vertex that does not have one in G, and otherwise using the same formula as above. This operation is, however, different from the one for simple graphs, since applying it to a graph with no self-loops would result in a graph with self-loops on all vertices.

...
Wikipedia