3. An independent set of a graph G is a subset I of the vertex set V such that no two vertices in I are adjacent. Let i(G) be the size of a maximal independent set of G. (a) Show that I is an...

3. An independent set of a graph G is a subset I of the vertex set V such that no two
vertices in I are adjacent. Let i(G) be the size of a maximal independent set of G.
(a) Show that I is an independent set of G if and only if V − I is a vertex cover
of G.
(b) Conclude from part (a) that i(G) + vc(G) = |V |.

Extracted text: 3. An independent set of a graph G is a subset I of the vertex set V such that no two vertices in I are adjacent. Let i(G) be the size of a maximal independent set of G. (a) Show that I is an independent set of G if and only if V – I is a vertex cover of G. (b) Conclude from part (a) that i(G) + vc(G) = |V|.