Feladat: 9.28.
Melyik állítás igaz az alábbiak közül:
Ha egy gráfban nincs
k+1 független pont, akkor az élei lefoghatók
a)
k ponttal;
b)
2k-1 ponttal,
c)
2k ponttal.
Segítség, útmutatás: 9.28
a) Egy háromszög már ellenpélda
k=1 esetben. Ebből minden esetre tudunk ellenpéldát mutatni a)-ra is, b)-re is.
c) Vegyünk egy maximális független élrendszert.