Feladat: 2.20.
a) Bizonyítsuk be, hogy ha egy
n pontú egyszerű gráfban nincs
C4
, és egy
x pontjának a foka
d, akkor az
x-szel összekötött pontokból induló élek száma legfeljebb
n-1+⌊d/2⌋.
Bizonyítsuk be, hogy
b)
e4
(8)=11, azaz ha egy nyolcpontú egyszerű gráfban legalább 12 él van, akkor van benne
C4
, de ugyanez nem minden 11 élű (nyolcpontú egyszerű) gráfra igaz.
c) Bizonyítsuk be, hogy
e4
(9)=13, azaz ha egy kilencpontú egyszerű gráfban legalább 14 él van, akkor van benne
C4
, de ugyanez nem minden 13 élű gráfra igaz.
Segítség, útmutatás: 2.20
a)-hoz használjuk a
3.18. feladat megoldásában használt gondolatmenetet.
b)-hez és c)-hez használjuk egyrészt a)-t, másrészt azt, hogy ha van legfeljebb másodfokú pont, akkor azt elhagyva
e4
(8) értéke visszavezethető
e4
(7)-re,
e4
(9) értéke pedig
e4
(8)-ra.