Megoldás: 3.10
n-re vonatkozó teljes indukcióval bizonyítunk. Ha
n=2, akkor
r(2,3)=3 igaz. Ha
n=3, akkor beláttuk, hogy
r(3,3)=6=(
4
2
). Ha
n=4, akkor azt is láttuk, hogy
r(4,3)=9<(
5
2
). Tegyük fel, hogy
n-1-re már tudjuk az állítást és legyen
G egy
(
n+1
2
) pontú gráf. Azt kell belátnunk, hogy vagy van benne
Kn
, vagy van benne három független pont.
Vegyünk egy tetszőleges
x pontot és tekintsük a vele össze nem kötött pontokat, ezek halmaza legyen
H. Ha
H valamely két pontja között nem fut él, akkor e két pont és
x egy független ponthármas. Ha viszont bármely két pontja között él, akkor
H pontjai teljes részgráfot alkotnak. Ha tehát
H-ban legalább
n pont van, akkor van a gráfban
Kn
.
Marad az az eset, amikor
H-nak legfeljebb
n-1 pontja van. Ez viszont azt jelenti, hogy
x legalább
(
n+1
2
)-n=(
n
2
) ponttal van összekötve. Az indukciós feltevésünk szerint tehát az általuk feszített részgráfban vagy van üres hármas, vagy van
Kn
. Ezzel az indukciós lépés bizonyítását befejeztük.