Graph/Paarungszahl/Knotenüberdeckungszahl/Vergleich/Fakt/Beweis

Beweis

Wenn eine Paarung mit ${}\pi (G)$ Kanten vorliegt, so sind diese disjunkt und eine Knotenüberdeckung muss jede der beteiligten Kanten treffen. Andererseits bilden die Endpunkte einer maximalen Paarung eine Knotenüberdeckung, da sie jede Kante treffen, denn andernfalls könnte man zu einer größeren Paarung gelangen.

Zur bewiesenen Aussage