Feladat: 2.4.
Legalább mekkora független ponthalmazt tudunk garantálni egy
n pontú egyszerű gráfban, amelyben minden pont foka legfeljebb
d?
Vagyis: melyik az a legnagyobb
m szám, amelyre igaz, hogy ha egy
n pontú egyszerű gráfban minden pont foka legfeljebb
d, akkor van benne
m pontú független ponthalmaz?