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 two adjacent vertices, i.e.: ∀u,v∈S:(u,v)∈E Example: Conversion Lemma Let G=(V,E) be a graph and S⊆V∧C=V−S. S is an independent set of G if and only if C is a vertex cover of G.
