3. FEJEZET: A skatulyaelv gráfelméleti élesítése, I.

Feladat: 3.1.
Bizonyítsuk be, hogy egy hattagú társaságnak mindig van vagy három olyan tagja, akik egymással ismeretségben vannak, vagy három olyan tagja, akik között nincs két ismeretségben levő. (Kürschák-verseny, 1947, [176]) Az ismeretséget kölcsönösnek feltételezzük.
 

Feladat: 3.2.
Egy öttagú társaságban nincs három ember, akik ismernék egymást, és nincs három ember, akik közül egyik sem ismerné a másikat. Bizonyítsuk be, hogy leültethetők egy kerek asztal köré úgy, hogy mindegyikük ismerje a két szomszédját, de ne ismerje a másik két embert.
 

Feladat: 3.3.
Bizonyítsuk be, hogy ha egy hatpontú teljes gráf éleit két színnel színezzük, akkor van három pont, amelyek között futó élek egyszínűek.
 

Feladat: 3.4.
Bizonyítsuk be, hogy ha egy hatpontú teljes gráf éleit két színnel színezzük, akkor van legalább két egyszínű háromszög. Van-e mindig három egyszínű háromszög is?
 

Feladat: 3.5.
a) Bizonyítsuk be, hogy ha egy tízpontú teljes gráfban nincs háromszög, akkor a komplementerében van négypontú teljes gráf. Vagyis 10→(3,4). b) Igaz-e ez kilencpontú gráfra is? c) Mi a helyzet nyolcpontú gráf esetén? (Arany Dániel-verseny 1994)
 

Feladat: 3.6.
Mutassuk meg, hogy ha egy 4-reguláris gráfban bármely pont szomszédai között két független él a komplementerben fut, akkor a gráfban nincs négypontú teljes részgráf.
 

Feladat: 3.7.
Mutassunk olyan nyolcpontú gráfot, amelyben nincs háromszög, és a komplementerében nincs négypontú teljes gráf. Vagyis mutassuk meg, hogy 8→(4,3) (és 8→(3,4)) nem igaz.
Jelölés. Bevezetjük a következő jelölést: r(n,k) jelöli azt a legkisebb pozitív r számot, amelyre igaz, hogy r→(n,k). Eddig beláttuk, hogy
 

Feladat: 3.8.
Tudjuk, hogy 9→(4,3) és 9→(3,4). Következik-e ebből, hogy a) 9→(4,4)? b) ha egy 9-pontú teljes gráf éleit úgy színezzük két színnel, hogy nincs egyszínű K4 , mind a két színből van egyszínű háromszög?
 

Feladat: 3.9.
Bizonyítsuk be, hogy r(n,2)=n.
 

Feladat: 3.10.
Bizonyítsuk be, hogy r(n,3)≤( n+1 2 ), ha n≥2.
 

Feladat: 3.11.
Bizonyítsuk be, hogy a) r(n,k)≤r(n,k-1)+r(n-1,k); b) r(n,k)≤( n+k-2 k-1 ), ha n,k≥2. (Erdős Pál és Szekeres György tétele.)
 

Feladat: 3.12.
a) Egy 17 tagú társaságból mindenki levelezik mindenkivel. A levelezés két ember között mindig ugyanazon a nyelven folyik, vagy franciául vagy németül vagy angolul. Bizonyítsuk be, hogy van három ember, akik ugyanazon a nyelven leveleznek egymással. (OKTV?)
Jelölés. Az állítás egyenértékű azzal, hogy ha egy 17 pontú teljes gráf éleit három színnel színezzük (minden él egy színt kap), akkor van egyszínű háromszög. Ezt így jelöljük: 17→(3,3,3).
 

Feladat: 3.13.
Legyen n>17. Bizonyítsuk be, hogy ha egy m pontú teljes gráf éleit három színnel színezzük, akkor a hármasoknak legalább a 680-ad része egyszínű lesz.
 

Feladat: 3.14.
Egy m csúcsú teljes gráf éleit akarjuk három színnel színezni úgy, hogy mind a három szín valóban elő is forduljon, de ne legyen ,,tarka" háromszög, azaz olyan háromszög, amelynek mind a három éle különböző. Lehetséges-e ez?
 

Feladat: 3.15.
* Újra felkeressük a K.II.19.32. feladat 3n+1 tagú társaságot, amelynek bármely két tagja vagy teniszezni, vagy sakkozni, vagy pingpongozni szokott egymással. Mindegyiküknek n tenisz-, n sakk- és n pingpongpartnere van. A feladat megoldásában láttuk, hogy a társaság tagjaiból legalább (3n+1)n olyan hármas állítható össze, amelyek egymás között mind a három játékot játsszák. Azt is láttuk, hogy ez nagy n-ekre elenyészően csekély, 2/(3n-1)-ed része az összes hármasnak. Vajon javítható-e az ottani eredményünk? Van-e olyan pozitív c szám, amelyre igaz, hogy a társaság tagjaiból kiválasztható legalább c( 3n+1 3 )-féleképp három úgy, hogy azok egymás között mind a három játékot játsszák (vagyis a hármasoknak legalább a c-ed része ,,tarka" hármas ebben az értelemben)?
 

Feladat: 3.16.
Hogyan általánosítható a 3.12. feladat állítása, ha n színnel színezzük a teljes gráfot és egyszínű háromszöget keresünk?
 

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.
 

Feladat: 3.18.
Bizonyítsuk be, hogy egy hat pontú gráfban, vagy a komplementerében van négy hosszú kör.
Jelölés. Ezt így jelöljük: 6→( C4 , C4 ). Általában m→( Ck , Cn ) jelöli azt, hogy egy m pontú teljes gráf éleit akárhogyan színezzük két színnel, vagy van az első színű k-pontú kör, vagy van a második színű n pontú kör.
 

Feladat: 3.19.
a) Bizonyítsuk be, hogy 5→( C4 , C4 ) nem igaz. b) Mutassuk meg, hogy 3n-2→( C2n , C2n ) nem igaz, tehát van olyan 3n-2 pontú gráf, amelyben nincs Cn és ez a komplementerére is igaz. c) Mutassuk meg, hogy 2n-2→( Cn , Cn ) nem igaz, ha n páratlan. Vagyis páratlan n-re van olyan 2n-2 pontú gráf, amelyben nincs Cn és a komplementerében sincs Cn .
Megjegyzés. Igaz viszont, hogy 3n-1→( C2n , C2n ), ha n≥3; valamint páratlan n-re 2n-1→( Cn , Cn ), ha n≥5. Ennek bizonyítása azonban sokkal bonyolultabb. Az alábbiakban (3.20.-3.28. feladat) néhány olyan feladatot mutatunk, amelyek legalább a bizonyítás gondolatvilágába bevezetnek.
 

Feladat: 3.20.
a) Bizonyítsuk be, hogy ha egy hatpontú gráfban van C5 , akkor vagy a gráfban, vagy a komplementerében van C4 is. b) Bizonyítsuk be, hogy ha egy gráfban van C6 , akkor vagy a gráfban, vagy a komplementerében van C4 is. c) Bizonyítsuk be, hogy ha egy gráfban valamely négynél nagyobb n-re van Cn és a gráf nem egy átló nélküli C5 , akkor vagy a gráfban, vagy a komplementerében van C4 .
 

Feladat: 3.21.
a) Bizonyítsuk be, hogy ha egy gráfban van C7 , akkor vagy a gráfban, vagy a komplementerében van C6 is. b) Bizonyítsuk be, hogy ha egy gráfban van C8 , akkor vagy a gráfban, vagy a komplementerében van C6 is.
 

Feladat: 3.22.
Bizonyítsuk be, hogy ha egy gráfban a) van C9 , akkor vagy a gráfban, vagy a komplementerében van C8 is; b) van C9 , akkor vagy a gráfban, vagy a komplementerében van C6 is; c) valamely ötnél nagyobb n-re van Cn , akkor vagy a gráfban, vagy a komplementerében van C6 ; d) van C10 , akkor vagy a gráfban, vagy a komplementerében van C8 .
 

Feladat: 3.23.
Bizonyítsuk be, hogy ha egy gráfban van C2n+2 , akkor vagy van benne C2n+1 is, vagy a gráfban, vagy a komplementerében van C2n .
 

Feladat: 3.24.
Bizonyítsuk be, hogy ha egy gráfban a) van C11 , akkor vagy a gráfban, vagy a komplementerében van C10 is; b) van C13 , akkor vagy a gráfban, vagy a komplementerében van C12 is; c) van C15 , akkor vagy a gráfban, vagy a komplementerében van C14 is; d) * van C2n+1 , ahol n legalább 3, akkor vagy a gráfban, vagy a komplementerében van C2n is.
 

Feladat: 3.25.
Mutassunk példát arra, hogy egy gráfban van C2k , de sem a gráfban, sem a komplementerében nincs C2k-1 .
Megjegyzés. Ha e feladat állítását összevetjük a 3.24. feladat d) részével, akkor jól láthatjuk, mennyivel ,,nehezebb" egy páratlan kört találni, mint párosat. Hogy páros kört mennyivel ,,könnyebb", ezt mutatja a 3.26. és a 3.26. feladat, továbbá összefoglalóan a 3.28. feladat.
 

Feladat: 3.26.
Bizonyítsuk be, hogy ha n legalább kettő és egy gráf tartalmaz C2n+2 -t, akkor vagy a gráf, vagy a komplementere tartalmaz C2n -et is.
 

Feladat: 3.27.
Legyen m>2n páros, n legalább kettő. Bizonyítandó, hogy ha egy gráf tartalmaz Cm -et, akkor vagy a gráf, vagy a komplementere tartalmaz C2n -et is.
 

Feladat: 3.28.
Legyen m>2n≥4. Bizonyítsuk be, hogy ha a gráf tartalmaz Cm -et és nem egyetlen átló nélkül ötszög, akkor vagy a gráf, vagy a komplementere tartalmaz C2n -et.
 

Feladat: 3.29.
Bizonyítsuk be Schur tételének következő két speciális esetét: a) Ha az első öt pozitív egész számot két csoportba osztjuk, akkor az egyik csoportban van megoldása az x+y=z egyenletnek. Azaz van három szám valamelyik csoportban, amelyek közül az egyik a másik kettő összege. (Az x=y esetet is megengedjük.) Vagy másképp fogalmazva: valamelyik csoportban van két szám, amelyek különbsége is ugyanabban a csoportban van. b) Egy versenyen 3 ország összesen 16 versenyzője indult. Bizonyítandó, hogy van egy olyan versenyző, akinek helyezése megegyezik két másik honfitársa helyezési számának az összegével, vagy kétszer akkora, mint egy honfitársa helyezési száma. c)* Egy nemzetközi társaságnak 1978 tagja van 6 különböző országból. A tagokat 1-től 1978-ig számozták meg. Mutassuk meg, hogy van legalább egy olyan tag, akinek a sorszáma megegyezik két honfitársa sorszámának az összegével, vagy kétszer akkora, mint egy honfitársa sorszáma. (IMO 1978/6.) d)* Igazoljuk Schur tételét az általános formájában: Schur-tétel. Ha n elég nagy és az első n pozitív számot k csoportba osztjuk, akkor valamelyik csoportban van megoldása az x+y=z egyenletnek, vagyis valamelyik csoportban van három szám, amelyek közül az egyik a másik kettő összege.
 

Feladat: 3.30.
* Bizonyítsuk be, hogy minden k pozitív egész számhoz van olyan Nk szám, amelyre igaz a következő: Akárhogyan is adunk meg több, mint Nk darab általános helyzetű pontot a síkon, azok között van k csúcs konvex sokszög.
 

Feladat: 3.31.
Adott egy d pozitív szám. Ezenkívül egy sík pontjait kiszíneztük két színnel. Bizonyítandó, hogy van két pont, A és B, amelyek azonos színűek és AB hossza pont d.
 

Feladat: 3.32.
Igaz-e a 3.31. feladat állítása akkor is, ha a sík pontjait három színnel színeztük?
 

Feladat: 3.33.
Bizonyítsuk be, hogy a sík pontjai kiszínezhetők két színnel úgy, hogy ne legyen olyan d oldalú szabályos háromszög, amelynek mindhárom csúcsa azonos színű.
 

Feladat: 3.34.
Adott egy d pozitív szám, továbbá kiszíneztük a sík pontjait két színnel. Bizonyítsuk be, hogy vagy van egy d oldalú szabályos háromszög, vagy van egy 2d oldalú szabályos háromszög, vagy van egy 3d oldalú szabályos háromszög, amelynek mindhárom csúcsa azonos színű.
 

Feladat: 3.35.
* A sík pontjait két színnel színeztük. Bizonyítsuk be, hogy pontosan akkor van olyan a, b, c oldalú háromszög, amelynek minden csúcsa azonos színű, ha vagy van a oldalú szabályos háromszög, vagy van b oldalú szabályos háromszög, vagy van c oldalú szabályos háromszög, amelynek minden csúcsa azonos színű.