if n=R(k,D,for any 2-coloring of Kn, there exists a red Kk or a blue Ki. R(k2)=k;R(2,)=I; R(k,)≤R(k,1-1)+R(k-1,) Ramsey Theorem R(k,l)is finite. By induction: R(k,L)≤ k+1-2 k-1 if n≥ R(k,l), for any 2-coloring of Kn, there exists a red Kk or a blue Kl. R(k,2) = k ; R(2,l) = l ; R(k,l) ≤ R(k,l-1) + R(k-1,l) Ramsey Theorem R(k,l) is finite. R(k,l) ⇥ k + l 2 k 1 By induction: ⇥