Definitions

# Complement graph

In graph theory 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 they are not adjacent in $G$. That is to find the complement of a graph, you fill in all the missing edges to get a complete graph, and remove all the edges that were already there. It is not the set complement of the graph; only the edges are complemented.

## Formal construction

Given graph $G\left(V_G, E_G\right)$ of vertices $V_G$ and edges $E_G$, construct its complement graph $H\left(V_H, E_H\right)$ by:

• $V_H = V_G$ and
• for a clique $K^n\left(V_K, E_K\right)$ of $n = |V_G|$ vertices, $E_H = E_K setminus E_G$.

The complement graph is used in several graph theories and demonstrations, such as the Ramsey theory, and different reductions for proofs of NP-Completeness.

Search another word or see Complement_graphon Dictionary | Thesaurus |Spanish