Für ein Vertexcover K V gilt: (i,j) E i K oder j K .
Ein Vertexcover heißt optimal |K| minimal.
(Vertexcover = Knotenüberdeckung)
hier |K| = 4 (optimal).
In bipartiten Graphen läßt sich aus einem Maximum-Matching ein minimales Vertexcover konstruieren.
Es gilt: Sei M ein Matching, K ein Vertexcover |M||K| .
Konstruktion: Siehe unten.