In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if

If and only if

In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

 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

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.-Properties:...

, and removes all the edges that were previously there. It is not, however, the set complement

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 of the graph; only the edges are complemented.

Formal construction

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.

Applications and examples

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

• The complement of an edgeless graph is a complete graph
  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.-Properties:...
  
   and vice versa.
• An independent set
  Independent set (graph theory)
  In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
  
   in a graph is a clique
  Clique (graph theory)
  In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
  
   in the complement graph and vice versa.
• The complement of any triangle-free graph
  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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
  
   is a claw-free graph.
• A self-complementary graph
  Self-complementary graph
  A self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph....
  
   is a graph that is isomorphic
  Graph isomorphism
  In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
  
   to its own complement.
• Cograph
  Cograph
  In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
  
  s are defined as the graphs that can be built up from disjoint union
  Disjoint union
  In mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a disjoint union...
  
  and complementation operations, and form a self-complementary family of graphs: the complement of any cograph is another (possibly different) cograph.