Let G be a graph. An independent set of G is a set of nodes in G such that no two nodes in the set are joined by an edge. Define I = { | G has an independent set with k elements }. Show that I is NP-complete as follows:

(a) Show that I is NP.

(b) For a graph G, define G* to the complementary graph of G; that is, two nodes u and v are joined by an edge in G* if and only if u and v are not joined by an edge in G. Show that for all positive integers k, G has a clique with k elements if and only if G* has an independent set with k elements.

(c) Using the above result, show that CLIQUE is polynomial-time mapping reducible to I.