A set of vertices is a vertex cover if and only if its complement is an independent set

Question

This following property is from wiki vertex cover: A set of vertices is a vertex cover if and only if its complement is an independent set.

I was wondering how do we prove that this is true? It would be great if it can be proved by contradiction but all other ways to prove are appreciated as well.

thank you!

Answer 1

Some hints:

• If I is an independent set and V - I isn't a vertex cover, then there's an edge where neither endpoint is in V - I. Therefore... ?

• If V - I is a vertex cover, then pick any edge. If both endpoints were in I, then ... ?

Best of luck!