„Ramsey-tétel” változatai közötti eltérés

 

=== ''R''₂(3,3,…,3) esete ===

Bebizonyítjuk az <math>R(3)\leq 3, R(3,3)\leq 6, R(3,3,3)\leq 17</math> és általában az <math>R(3,3,\dots,3)\leq [er!]+1</math> becslést (az első három esetben egyenlőség van). Ehhez definiáljuk az ''f'' függvényt az <math>f(1)=2</math>, <math>f(r+1)=(r+1)f(r)+1</math> rekurzióval. ''r''-re való indukcióval bebizonyítjuk, hogy ha <math>K_{f(r)+1}</math> éleit ''r'' színnel színezzük, van egyszínű háromszög. Ez ''r''=1-re nyilván igaz. Tegyük fel, hogy tudjuk az állítást ''r''-re és adott <math>K_{f(r+1)+1}</math> éleinek egy ''r''+1 színnel való színezése. Legyen ''p'' a gráf egy csúcsa, <math>A_1,\dots,A_{r+1}</math> sorra azon további pontok halmaza, amelyek ''p''-be az első, második, …, ''r''+1-edik színben vannak bekötve. Nyilván <math>|A_1|+\cdots+|A_{r+1}|=f(r+1)=(r+1)f(r)+1</math>, ezért van olyan <math>i</math>,

hogy <math>|A_i|\geq f(r)+1</math>. Ha <math>A_i</math> pontjai között szerepelne az ''i''-edik szín, akkor van az ''i'' színben háromszög. Ha nem, <math>A_i</math> párjait ''r'' színnel színezzük, az indukció miatt van tehát egyszínű háromszög.