graph-theory Definition Independent Set The independent set of a graph G=(V,E) is the subset S⊆V, s.t. there do not exist to adjacent vertices.