Cliques in G are independent sets in the complement

Statement

Lemma

For a undirected graph and we have the following equivalence: is a clique in if and only if is an independent set in the complement graph.

Proof

Suppose is clique in then for all with . As then for all with we have so is a independent set in .

Similarly if is an independent set in then for all with . Therefore by definition , and we have is a clique.