graph-theory Definition Vertex Cover A vertex cover of a graph G=(V,E) is the set S⊆V, such that every edge e∈V incident to at least one v∈S. 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.