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.