Complement graph

Definition

Let $G = (V, E)$ be a graph. The complement of $G$ is the graph $\overline{G}$ with vertex set $V$. Two distinct vertices are adjacent in $\overline{G}$ if and only if they are not adjacent in $G$.

Remarks

The complement of the complement of $G$ is $G$. The complement of the complete graph $K_n$ is the graph on $n$ vertices with no edges. A clique of $G$ is an independent set of $\overline{G}$. This links Ramsey numbers to colourings of $K_n$.

Explanations

L1 human

To get the complement, remove all edges of the graph and draw all the missing ones. If $G$ records which people know each other, then $\overline{G}$ records which people are strangers.