Megoldás: 1.36
A tételt (ebben a formájában) nyilván elég
megszámlálhatóan végtelen gráfra (vagyis olyan gráfra, amelynek csúcshalmaza - s így élhalmaza is - megszámlálható) bebizonyítani.
Számozzuk meg a csúcsokat a természetes számokkal. Mivel a csúcshalmaz megszámlálható, ezt megtehetjük. Vegyük az egyes számú pontot (a továbbiak kedvéért
x1
-gyel jelöljük), és nézzük meg, hogy a gráfban végtelen sok ponttal van-e összekötve. Ha igen, írjunk rá egy plusz jelet és hagyjuk el azokat a pontokat, amelyekkel nincs összekötve. Ha az egyes számú pont a gráfban csak véges sok ponttal van összekötve, akkor írjunk rá egy mínusz jelet és hagyjuk el azokat a pontokat, amelyekkel össze van kötve. Mindkét esetben jelöljük
H1
-gyel a maradó halmazt, ez mindkét esetben végtelen halmaz.
Most keressük meg a
H1
halmaz legkisebb számú elemét, legyen ez
x2
, és nézzük meg, hogy végtelen sok
H1
-beli ponttal van-e összekötve. Ha igen, hagyjuk el a többi pontot, és írjunk erre a pontra egy plusz jelet, ha viszont csak véges sok ponttal van összekötve, hagyjuk el ezeket, és írjunk az
x2
pontra egy mínusz jelet. A maradó ponthalmazt jelöljük
H2
-vel. Ez a halmaz továbbra is végtelen halmaz, és igaz rá, hogy ha
x2
-re plusz jel van írva, akkor minden
H2
-beli pont össze van vele kötve, ha mínusz, akkor
H2
egyik pontja sincs összekötve vele, és ugyanez igaz
x1
-re is.
Ezt az eljárást folytatva teljes indukcióval minden
n-re kiválasztunk egy
xn
pontot
Hn-1
-ből, és hozzá
Hn-1
egy végtelen
Hn
részhalmazát úgy, hogy igaz maradjon az, hogy ha
xi
-re plusz jel van írva, akkor
Hn
minden pontja össze van kötve vele, ha mínusz jel van rá írva, akkor
Hn
egyik pontja sincs összekötve vele. Minthogy
Hn-1
végtelen, ezt nyilván továbbra is ugyanúgy megtehetjük, mint az első két esetben: legyen
Hn-1
legkisebb pontja
xn
. Ha
xn
a
Hn-1
ponthalmaz végtelen sok pontjával van összekötve, akkor plusz jelet írunk rá és elhagyjuk a többi pontot, ha viszont
Hn-1
-nek csak véges sok pontjával van összekötve, akkor ezeket hagyjuk el és
xn
-re mínusz jelet írunk. A maradó ponthalmaz lesz
Hn
.
Így teljes indukcióval kiválasztjuk a gráf egy végtelen
ponthalmazát. Mivel minden
n-nél nagyobb indexű pontot
Hn
-ből (egy részhalmazából) választottuk, ezért igaz a következő: ha
xn
-re plusz jelet írtunk, akkor minden
n-nél nagyobb indexű ponttal össze van kötve, ha mínusz jelet írtunk rá, akkor egyetlen nagyobb indexű ponttal sincs összekötve. Tehát a plusz jelű pontok egy teljes részgráfot alkotnak, míg a mínusz jelűek a komplementerben alkotnak teljes részgráfot. E két ponthalmaz valamelyike végtelen (hiszen uniójuk végtelen: kiadja az összes
xn
pontot), tehát vagy a gráfban, vagy a komplementerében találtunk végtelen részgráfot.
1. megjegyzés: A tételt tehát csak megszámlálhatóan végtelen gráfokra bizonyítottuk be. De minden végtelen gráfnak van megszámlálhatóan végtelen részgráfja, így ez elég is az általánosabb tétel bizonyításához.
A tétel azonban ennél erősebb alakban is igaz:
Végtelen Ramsey-tétel/2: Bármely egyszerű végtelen gráfra igaz, hogy vagy maga a gráf tartalmaz egy, a gráf csúcshalmazával azonos számosságú teljes részgráfot, vagy a komplementere tartalmaz egy megszámlálhatóan végtelen teljes részgráfot. Az állítás így is fogalmazható: egy
ℵ számosságú egyszerű gráf vagy tartalmaz
ℵ számosságú teljes részgráfot, vagy tartalmaz üres megszámlálható részgráfot.
Ennek az erősebb tételnek a bizonyításához már nem elég az egyszerű teljes indukció, úgynevezett transzfinit indukcióra van szükség. Ezt itt nem részletezzük.
Az viszont általában nem igaz, hogy egy végtelen gráfban vagy a komplementerében van a csúcshalmazzal azonos számosságú teljes részgráf. Sőt, a halmazelmélet axiómáival összeegyeztethető, hogy ez csakis a megszámlálható számosságú gráfokra igaz.
2. megjegyzés: E tételek felhasználásával könnyen bizonyítható, hogy ha egy megszámlálhatóan végtelen gráf éleit
k színnel színezzük, akkor valamelyik színből van teljes végtelen részgráf. Másrészt ha egy
ℵ számosságú gráf éleit színezzük
k színnel, akkor vagy az első színből van
ℵ számosságú teljes részgráf, vagy valamelyik másik színből megszámlálhatóan végtelen teljes részgráf.
3. megjegyzés: Ugyanúgy, ahogy véges gráfokra, végtelen gráfokra is felvethető a kérdés, hogy adott
ℵa
és
ℵb
számosság esetén milyen
ℵ számosságú gráfokra tudjuk garantálni, hogy ha a gráf éleit két színnel színezzük, vagy van első színű
ℵa
számosságú teljes részgráf, vagy van második színű
ℵb
számosságú teljes részgráf. Természetesen ezek a kérdések is általánosíthatók több színnel való színezésre. A kérdésnek nagy irodalma van.