Complement graph

Petersen graph (left) and its complement graph (right).

As a complement graph , complementary graph or complement is referred to in the graph theory a particular graph , obtained from a given graph.

The complementary graph has the same nodes as the original graph , but differs in its edges : The complement graph has exactly those edges that the original graph does not have.

definition

Let be an undirected or directed graph without multiple edges . The undirected or directed graph without multiple edges is called the complement graph of if the intersection of and is empty and the union of and ${\displaystyle G_{1}=(V,E_{1})}$ ${\displaystyle G_{2}=(V,E_{2})}$ ${\displaystyle G_{1}}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$ ${\displaystyle E_{1}}$ ${\displaystyle E_{2}}$

• in the undirected case the set of all 2-element subsets of V resp.
• in the directed case, the Cartesian product ${\displaystyle V\times V}$

results.

The complement graph of a given graph is often referred to as. As a self-complementary refers graphs isomorphic complementary to their graphs. ${\displaystyle G}$ ${\displaystyle {\overline {G}}}$

properties

• The complement of the complement of G is G itself.