Megoldás: 3.11
a) Alkalmazzuk ebben az esetben is a
3.10. feladat gondolatmenetét. Vegyünk egy
r(n,k-1)+r(n-1,k) pontú egyszerű gráfot és annak egy
x pontját. Tekintsük a vele össze nem kötött pontok által feszített részgráfot. Ha ebben van
Kn
, akkor kész vagyunk. Ha van
k-1 független pont, akkor ezek
x-szel együtt
k független pontot alkotnak, és megint kész vagyunk. Ha viszont egyik sem teljesül, akkor legfeljebb
r(n,k-1)-1 ponttal nincs összekötve
x, tehát legalább
r(n-1,k) ponttal össze van kötve. Vagyis a szomszédai által feszített részgráfban vagy van
Kn-1
, s ennek pontjai
x-szel kiegészítve egy
Kn
-et alkotnak, vagy van
k független pont. Tehát minden esetben kész vagyunk a bizonyítással.
a)-ból b) a Pascal-háromszög képzési szabálya szerint következik teljes indukcióval.