Definition:Complement (Graph Theory)/Simple Graph
< Definition:Complement (Graph Theory)(Redirected from Definition:Complement of Simple Graph)
Jump to navigation
Jump to search
Definition
Let $G = \struct {V, E}$ be a simple graph.
The complement of $G$ is the simple 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$, where $u$ and $v$ are distinct.
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.