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.