Feladat: 14.25.
Egy egyszerű végtelen gráf minden véges része három színnel jól színezhető. Rögzítsük minden véges részgráf egy három színnel való jószínezését, a továbbiakban csak ezt a kiválasztott színezést tekintjük jólszínezésnek.
A) Bizonyítsuk be, hogy bárhogy választunk ki egy
x pontot, ahhoz hozzárendelhetjük a három szín egyikét úgy, hogy van
tetszőlegesen nagy,
x-et tartalmazó részgráf, amelynek jólszínezésében
x ezzel a színnel van színezve.
B) Rendeljünk ilymódon hozzá minden ponthoz egy-egy színt. Mutassunk példát arra, hogy a végtelen gráf ilymódon kapott színezése nem jólszínezése a gráfnak!
C) Megadható-e végtelen sok páronként különböző halmaz úgy, bárhogyan választunk ki közülük végtelen sokat, azok uniója megegyezik az eredeti végtelen sok halmaz uniójával?
D) Próbáljuk most eldönteni a
14.23. feladatban feltett kérdést!
Segítség, útmutatás: 14.25
Az A) feladat megoldásához használjuk a végtelen skatyulaelvet.
B) feladat: Könyen előfordulhat, hogy A) eljárásával
bármely ponthoz hozzárendelhető
ugyanaz a szín. Mutassunk erre példát.
C) feladat: Ha egy elem végtelen sok halmazban nem szerepel, akkor ezt a végtelen sok halmazt kiválasztva az unió kisebb lesz az összes halmaz uniójánál. Tehát arra kell törekednünk, hogy minden elem csak véges sok halmazban NE szerepeljen.
D) feladat: Válasszuk
Gn
-nek az első
n csúcs által feszített részgráfot és ezekre alkalmazzuk A) állítást, majd használjuk C)-t, és ismételjük ezt az eljárást a második, a harmadik stb. pontra.