Complement graph
![](https://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Petersen_graph_complement.svg/220px-Petersen_graph_complement.svg.png)
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
- in the undirected case the set of all 2-element subsets of V resp.
- in the directed case, the Cartesian product
results.
The complement graph of a given graph is often referred to as. As a self-complementary refers graphs isomorphic complementary to their graphs.
properties
- The complement of the complement of G is G itself.