Graph/Paarungszahl/Knotenüberdeckungszahl/Vergleich/Fakt

In einem Graphen

gelten zwischen der Knotenüberdeckungszahl ${}\kappa (G)$ und der Paarungszahl ${}\pi (G)$ die Abschätzungen

${}\pi (G)\leq \kappa (G)\leq 2\pi (G)\,.$

Zum Beweis, Alternativen Beweis erstellen