Consider the problem of "Independent set" in grahps. Given a graph $G$ and an integer $k$, the machine determines whether the graph $G$ contains an independent set of size $k$.
I need to prove that it's in NP-Complete by showing a reduction from another known language in NP-Complete (vertex cover, clique, sat) to IS problem. which one would you suggest?
Thanks in advance
Vertex cover. If $S$ is a vertex cover of $G$ of size $|V(G)| - k$, then the collection of vertices of $G$ not in $S$ must form an independent set (why?) of size $k$.