Vertex cover if and only if the complement is an independent set

Statement

Lemma

Suppose we have an undirected graph with . Then is a vertex cover if and only if is an independent set.

Proof

Suppose is a vertex cover.

For all either or , therefore no edge in connects two vertices in making an independent set.

Suppose is an independent set.

Let , as is an independent set either or . Therefore is a vertex cover by definition.