Proof between max independent set cardinal and min vertex cover.

Question

i'm tryign to solve this problem for my graph class, but I don't really know where to start.

Be G a graph without isolated vertex,proof that it verifies that $\alpha \leq \beta$, where $\alpha$ is the cardinal of the max idependent set, and $\beta$ the cardinal of the minimum vetex cover.

Could you give me a hint of where to start?

Answer 1

Hint:

• Complement of any independent set is a vertex cover.
• Complement of any vertex cover is an independent set.

I hope this helps $\ddot\smile$