It is easy to verify that IS is in *NP*. To see that IS is *NP*-complete, we reduce VC to it. For any given graph and given integer *K* ≥ 0, we observe that a subset is a vertex cover of *G* if and only if is an independent set of *G*. In other words, *G* has a vertex cover of size *K* if and only if *G* has an independent set of size , and so the function mapping (*G*,*K*) to reduces VC to IS. Thus, IS is *NP*-complete.

For any graph , let *G*^{c} be its complement graph, that is, let , where . Then, a subset is an independent set of *G* if and only if ...