Definition:Complement (Graph Theory)/Loop-Graph

From ProofWiki
Jump to navigation Jump to search

Definition

Let $G = \struct {V, E}$ be a loop-graph.

The complement of $G$ is the loop-graph $\overline G = \struct {V, \overline E}$ which consists of:

The same vertex set $V$ of $G$;
The set $\overline E$ defined such that:
$\set {u, v} \in \overline E \iff \set {u, v} \notin E$
$\set {v, v} \in \overline E \iff \set {v, v} \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.