Megoldás: 2.5
a)
n-re vonatkozó teljes indukcióval bizonyítunk.
n=2-re az állítás tautológia. Tegyük fel, hogy
2n-2 pontú gráfokra már tudjuk az állítást és legyen
G egy
2n pontú gráf, amelynek több, mint
n2
éle van. Az
1.10. feladat gondolatmenetét alkalmazzuk. Legyen
x és
y két éllel összekötött pont. Ha az
x-ből és
y-ból induló élek száma legfeljebb
2n-1, akkor elhagyhatjuk a gráfból e két pontot a belőlük induló élekkel együtt, s a maradó
2n-2=2(n-1) pontú gráfban több, mint
n2
-2n+1=(n-1
)2
él van, tehát az indukciós feltevés szerint van benne megfelelő pontnégyes.
Akkor van csak ,,baj", ha
x-ből és
y-ból együtt legalább
2n él indul. Nézzük, ez hogyan lehetséges. Egy él köti össze őket, tehát ,,kifele" legalább
2n-1 él indul a maradó
2n-2 pontba. Ez azt jelenti, hogy legalább egy közös szomszédjuk van. Ha legalább kettő van, akkor két közös szomszéd és
x,y egy megfelelő pontnégyes. Tehát feltehetjük a továbbiakban, hogy
x-nek és
y-nak pontosan egy közös szomszédjuk van, legyen ez
z.
x,y,z tehát egy háromszöget alkot, ez három él, a maradó
2n-3 pontba
x és
y közül legfeljebb az egyikből indul él. Viszont legalább
2n-3 él indul ki a maradó
2n-3 pontba, tehát minden további pontba pontosan az egyikükből indul él. Ha tehát
z-ből egy további
u pontba indul él, akkor
x,y,z,u egy megfelelő pontnégyes. Megint kész vagyunk, kivéve, ha
z másodfokú. De akkor
x és
y helyett ugyanezt
y és
z-re elmondva azt kapnánk, hogy
x is másodfokú, továbbá ugyanígy
y is másodfokú, vagyis bármely pont, amelyből indul ki él, másodfokú és a gráf pontdiszjunkt háromszögekből áll. Az élszáma tehát
2n. Ez viszont
n>1 esetén nem több, mint
n2
. Ezzel a feladat a) részének állítását bebizonyítottuk.
Ha van két közös szomszédjuk, akkor e két közös szomszéd és
x,y egy megfelelő pontnégyes. Ha egy közös szomszédjuk van és van egy pont, amellyel sem
x, sem
y nincs összekötve, akkor számoljuk össze azokat az éleket, amelyek egyik végpontja
x vagy
y. Van a kettőt összekötő él, van a közös szomszédba futó két él és van még legfeljebb
2n-4 él, hiszen van legalább egy pont, amellyel egyikük sincs összekötve. Ez azt jelenti, hogy legfeljebb
2n-1 él indul
x-ből és
y-ból. Ugyanez a helyzet akkor is, ha
x-nek és
y-nak nincs közös szomszédja. Hagyjuk el tehát
x-et és
y-t a belőlük induló élekkel együtt a gráfból. A maradó
2n-2=2(n-1) pontú gráfban több, mint
n2
-2n+1=(n-1
)2
él van, tehát az indukciós feltevés szerint van benne megfelelő pontnégyes.
Maradt az az eset, amikor
b) Most is jó az a teljes páros gráf, amelynek mindkét osztályában
n pont van.