In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the complement or inverse of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

is a graph on the same vertices such that two distinct vertices of are adjacent

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

they are not adjacent in . That is, to generate the complement of a graph, one fills in all the missing edges required to form a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

, and removes all the edges that were previously there.. The complement is not the

set complement In set theory, the complement of a set , often denoted by A^c (or ), is the set of elements not in . When all elements in the universe, i.e. all elements under consideration, are considered to be members of a given set , the absolute complemen ...

of the graph; only the edges are complemented.

Definition

Let be a

simple graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a Set (mathematics), set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''Ver ...

and let consist of all 2-element subsets of . Then is the complement of , where is the

relative complement In set theory, the complement of a set , often denoted by A^c (or ), is the set of elements not in . When all elements in the universe, i.e. all elements under consideration, are considered to be members of a given set , the absolute complement ...

of in . 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 pair In mathematics, an ordered pair, denoted (''a'', ''b''), is a pair of objects in which their order is significant. The ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a''), unless ''a'' = ''b''. In contrast, the '' unord ...

s of in place of the set in the formula above. In terms of the

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...

''A'' of the graph, if ''Q'' is the adjacency matrix of the

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''. The complement is not defined for

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...

s. In graphs that allow self-loops (but not multiple adjacencies) the complement of may be defined by adding a self-loop to every vertex that does not have one in , 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.

Applications and examples

Several graph-theoretic concepts are related to each other via complementation: *The complement of an edgeless graph is a

and vice versa. *Any

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

of the complement graph of a graph is the complement of the corresponding induced subgraph in . *An independent set in a graph is a

clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

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 In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphism ...

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

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

is a

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...

, although the reverse is not true.

Self-complementary graphs and graph classes

self-complementary graph In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the path graph and the cycle graph. There is no known characteri ...

is a graph that is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

to its own complement. Examples include the four-vertex

path graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

and five-vertex

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

. There is no known characterization of self-complementary graphs. Several classes of graphs are self-complementary, in the sense that the complement of any graph in one of these classes is another graph in the same class. *

Perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

s are the graphs in which, for every induced subgraph, the

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

equals the size of the maximum clique. The fact that the complement of a perfect graph is also perfect is the perfect graph theorem of

László Lovász László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He ...

. *

Cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

s are defined as the graphs that can be built up from single vertices by

disjoint union In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...

and complementation operations. They form a self-complementary family of graphs: the complement of any cograph is another different cograph. For cographs of more than one vertex, exactly one graph in each complementary pair is connected, and one equivalent definition of cographs is that each of their connected

s has a disconnected complement. Another, self-complementary definition is that they are the graphs with no induced subgraph in the form of a four-vertex path. *Another self-complementary class of graphs is the class of

split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by , where they called these ...

s, the graphs in which the vertices can be partitioned into a clique and an independent set. The same partition gives an independent set and a clique in the complement graph. *The

threshold graph In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: # Addition of a single isolated vertex to the graph. # Addition of a single dominating vertex ...

s are the graphs formed by repeatedly adding either an independent vertex (one with no neighbors) or a

universal vertex In graph theory, a universal vertex is a Vertex (graph theory), vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. A ...

(adjacent to all previously-added vertices). These two operations are complementary and they generate a self-complementary class of graphs.

Algorithmic aspects

In the

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

on graphs, the distinction between a graph and its complement is an important one, because a

sparse graph In mathematics, a dense graph is a Graph (discrete mathematics), graph in which the number of edges is close to the maximal number of edges (where every pair of Vertex (graph theory), vertices is connected by one edge). The opposite, a graph with ...

(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. Therefore, researchers have studied algorithms that perform standard graph computations on the complement of an input graph, using an

implicit graph In the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices or edges are not represented as explicit objects in a computer's memo ...

representation that does not require the explicit construction of the complement graph. In particular, it is possible to simulate either

depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...

breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next dept ...

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. It is also possible to use these simulations to compute other properties concerning the connectivity of the complement graph...

References

{{reflist, 30em Graph operations