The complement of a graph , sometimes called the edge-complement (Gross and Yellen 2006, p. 86), is the graph , sometimes denoted or (e.g., Clark and Entringer 1983), with the same vertex set but whose edge set consists of the edges not present in (i.e., the complement of the edge set of with respect to all possible edges on the vertex set of ). The graph sum on a -node graph is therefore the complete graph , as illustrated above.
The adjacency matrix of the graph complement of the graph with adjacency matrix is given by
(Ellis-Monaghan and Merino 2008), where is the unit matrix and is the identity matrix.
A graph complement can be computed in the Wolfram Language by the command GraphComplement[g].