Feladat: 3.17.
* Bizonyítsuk be a Ramsey-tétel következő, véges (egyszerű) gráfokra vonatkozó legáltalánosabb alakját: Általános Ramsey-tétel gráfokra. Akárhogyan adunk meg egy pozitív egész k számot, továbbá akárhogyan adjuk meg az n1 , n2 ,…, nk ≥2 egész számokat, van olyan m szám, amelyre (és minden nála nagyobbra) igaz, hogy Szavakkal: van olyan m szám, hogy ha egy m pontú teljes gráfot kiszínezünk k színnel (egy él egy színt kap), akkor valamelyik i-re van ni pontú teljes részgráf, amelynek minden éle i színű.
Jelölés. A legkisebb olyan m számot, amelyre ez az állítás teljesül, r( n1 , n2 .…, nk )-val jelöljük.

Megjegyzés. Az állítás általánosítható úgynevezett hipergráfokra is, ekkor azt mondja ki, hogy ha egy m pontú halmaz minden l pontú részhalmazát kiszínezzük k szín valamelyikével, akkor valamelyik i-re van olyan ni elemű részhalmaz, amelynek minden l elemű részhalmaza i színű. Ez a Ramsey-tétel l-hipergráfokra.
 

Megoldás: 3.17
Ha az ni számok egy kivételével 2-vel egyenlők, akkor az r(2,…,2, ni ,2,…,2-függvény értéke n. Hiszen az állítás éppen azt mondja ki, hogy vagy minden él az i-edik színt kapta, vagy van más színű él is. Másrészt a 3.11. feladat gondolatmenete átvihető több színre is, és akkor azt kapjuk, hogy Vegyünk ugyanis egy

r( n1 -1, n2 ,…, nk )+r( n1 , n2 -1,…, nk )+…+r( n1 , n2 ,…, nk -1)

pontú teljes gráfot és színezzük ki éleit k színnel tetszőlgesen. Vegyünk egy x pontot és nézzük a belőle kiinduló első színű éleket. Ha ezekből legalább r( n1 -1, n2 ,…, nk ) darab van, akkor ezek végpontjai között vagy van első színű teljes n1 -1-es és akkor x-et hozzávéve van teljes n1 -es, vagy valamelyik másik i-re van i színű teljes ni pontú rész. Ugyanígy járhatunk el bármelyik más szín esetén. Ha viszont minden i-re kevesebb volna az i színű éllel összekötött szomszédok száma, akkor a gráf pontszáma is kevesebb volna a megadottnál. Innen az összes ni -re vonatkozó teljes indukcióval az általános Ramsey-tétel nyilvánvalóan következik.