Ramsey sayıları için naçizane bir üst limit

R(k,k) <= 2R(k,k-1)

Kanıt :
2R(k,k-1) düğümlü iki renkli tamamlanmış bir çizgeyi ele alalım. Bu çizgenin herhangi bir düğümü (D düğümü diyelim) tek-renk olan en az R(k,k-1) tane kenar barındırır. (Güvercin yuvası ilkesi)

Bu tek-renk kenarlarların bir uçları aynı düğümde olduğuna göre diğer uçları tamamen farklı düğümlerde sonlanmalıdır.

R(k,k-1) düğümün oluşturduğu bu alt çizgeyi (Ç diyelim) inceleyelim.

R(k,k) nın koşuluna bakalım. Bu çizge en azından k düğümlü tek-renk tamamlanmış bir alt-çizge
barındırmalıdır.

R(k,k-1) in koşullarına bakalım. Bu çizge en azından a renkli k düğümlü yada b renkli k-1 düğümlü bir
alt-çizge barındırmalıdır.

R(k,k-1) = R(k-1,k) olduğuna göre
D düğümüne bağlı tek-renkli R(k,k-1) tane kenarın rengi

• a ise R(k-1,k) dan dolayı :
  

  • Ç çizgesi b renkli k düğümlü bir alt-çizge barındırır ya da

  • Ç çizgesi a renkli k-1 düğümlü bir alt çizge barındırır ve bu alt çizgeye D düğümü ilave edilirse k düğümlü a renkli bir alt çizge elde edilir.

• b ise R(k,k-1) den dolayı :

  • Ç çizgesi a renkli k düğümlü bir alt-çizge barındırır ya da

  • Ç çizgesi b renkli k-1 düğümlü bir alt çizge barındırır ve bu alt çizgeye D düğümü ilave edilirse k düğümlü b renkli bir alt çizge elde edilir.

Görüldüğü gibi her durumda k düğümlü tek-renk bir alt çizge kaçınılmazdır.
O halde R(k,k) <= 2R(k,k-1) 'dir.