Duale Schranke

Angenommen, $G$ enthält ein matching $M$ der Größe $k$ .
Da jede Kante $e \in M$ paarweise knotendisjunkt ist, muss ein gültiges vertex cover $X$ aus jeder dieser Kanten mindestens einen Endknoten enthalten.
Daraus folgt direkt die fundamentale relationale Schranke:

| X | \geq k