Feladat: 3.10.
Bizonyítsuk be, hogy r(n,3)≤( n+1 2 ), ha n≥2.
 

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.