Statement

Lemma

Suppose we have an undirected graph $G = (V,E)$ with $C \subset V$. Then $C$ is a vertex cover if and only if $\overline{C} := V \backslash C$ is an independent set.

Proof

Suppose $C$ is a vertex cover.

For all $(u,v) \in E$ either $u \in C$ or $v \in C$, therefore no edge in $E$ connects two vertices in $\overline{C}$ making $\overline{C}$ an independent set.

Suppose $\overline{C}$ is an independent set.

Let $(u,v) \in E$, as $\overline{C}$ is an independent set either $u \in C$ or $v \in C$. Therefore $C$ is a vertex cover by definition.