Statement

Lemma

For a undirected graph $G = (V,E)$ and $S \subset V$ we have the following equivalence: $S$ is a clique in $G$ if and only if $S$ is an independent set in $G^C$ the complement graph.

Proof

Suppose $S$ is clique in $G$ then $(s,s') \in E$ for all $s, s' \in S$ with $s \not = s'$. As

$$G^C = (V, \overline{E} := \{(u,v) \in V \times V \vert (u,v) \not \in E\})$$

then for all $s, s' \in S$ with $s \not = s'$ we have $(s,s') \not \in \overline{E}$ so $S$ is a independent set in $G^C$.

Similarly if $S$ is an independent set in $G^C$ then $(s,s') \not \in E'$ for all $s, s' \in S$ with $s \not = s'$. Therefore by definition $(s,s') \in E$, and we have $S$ is a clique.