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. Example: In the graph below, the set S={v2,v4} is a vertex cover, as every edge is incident to either v2 or v4. 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.