Recall that a problem is NP-complete if it is in NP and every problem in NP can be reduced to it in polynomial time. Start by showing that the independent set problem is in NP.

To prove NP-hardness, consider a known NP-complete problem (e.g., Clique or 3-SAT) and construct a polynomial-time reduction from it to the independent set problem.

For the reduction, define a transformation that maps instances of the known NP-complete problem to instances of the independent set problem while preserving the "yes" or "no" answer, ensuring the transformation runs in polynomial time.