# Definition:Complement (Graph Theory)

Jump to navigation
Jump to search

## Definition

### Simple Graph

Let $G = \left({V, E}\right)$ be a simple graph.

The **complement of $G$** is the simple graph $\overline{G} = \left({V, \overline{E}}\right)$ which consists of:

- The same vertex set $V$ of $G$
- The set $\overline{E}$ defined such that $\left\{{u, v}\right\} \in \overline{E} \iff \left\{{u, v}\right\} \notin E$, where $u$ and $v$ are distinct.

### Loop-Graph

If $G = \left({V, E}\right)$ is a loop-graph, the concept is slightly different.

The **complement of $G$** is the simple graph $\overline{G} = \left({V, \overline{E}}\right)$ which consists of:

- The same vertex set $V$ of $G$;
- The set $\overline{E}$ defined such that:
- $\left\{{u, v}\right\} \in \overline{E} \iff \left\{{u, v}\right\} \notin E$;
- $\left\{{v, v}\right\} \in \overline{E} \iff \left\{{v, v}\right\} \notin E$.

That is, the complement $\overline{G}$ of a loop-graph $G$ has loops on all vertices where there are no loops in $G$.

## Linguistic Note

The word **complement** comes from the idea of **complete-ment**, it being the thing needed to **complete** something else.

It is a common mistake to confuse the words **complement** and **compliment**. Usually the latter is mistakenly used when the former is meant.