Let G = (V, E) be an undirected graph. An independent set (independent set) I V is a subset of the nodes, so that no two nodes from I are connected by an edge. For a given graph G and a natural number k |V | the problem IS is the question whether G has a k-element independent set. Prove: IS is NP-complete. Note: Reduce 3-CNF-SAT to IS.