# Proving that the independent set problem is in NP-Complete

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?

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$.
• Yes. Going the other way, if $I$ is your independent set of size $k$, then the vertices not in $I$ must cover all edges of $G$ since by the definition of independent set, vertices in $I$ can share no edges with each other. – Shil B. May 22 '13 at 17:17