An
independent set, in
graph theory, is a set of vertices that are not
connected to each other by an
edge. Any set with exactly one
vertex is an independent set.
The independent set problem is: given a graph and an integer k, is there an independent set with the number of vertices >= k?
The independent set problem has been proven to be np-complete by a reduction from clique.