📂Graph Theory

Graph Complement

Definition ¹

For a simple graph $G$, a graph $\overline{G}$ that satisfies the following conditions is called the complement of $G$. $$ V \left( \overline{G} \right) = V(G) \\ vw \in E \left( \overline{G} \right) \iff vw \notin E(G) $$

Description

As with the concept of Complement in mathematics, the complement of a graph implies the concept of supplement. If we were to translate it into more native Korean, it would be Complement Graph, but none seemed fitting, hence the term complement is used as is.

It’s not difficult to understand intuitively just by looking at the diagram, but there could be slightly uncomfortable parts when explaining solely through equations. By introducing this expression, it becomes more convenient and easy to handle graphs. Let’s look at the following illustration as an example of a complement graph:

The two graphs $G$ and $\overline{G}$ have the same vertices but have exactly opposite edges. In this explanation, saying ’exactly opposite’ might not sound mathematically rigorous. Although it would be mathematically neat to explain it as $$ vw \in E \left( \overline{G} \right) \iff vw \notin E(G) $$ it becomes slightly harder to read naturally. Instead, simply calling it a complement allows for understanding with one example and facilitates the continuation of mathematical discussion without equations.