1. FEJEZET: A skatulyaelv a gráfelméletben, I.

Feladat: 1.1.
a) Igazoljuk, hogy egy véges egyszerű gráfban mindig van két azonos fokú pont. b) Mutassunk példát olyan n pontú gráfra, amelyben csak egyetlen azonos fokú pontpár van.
 

Feladat: 1.2.
a) Az 1.1. feladatban a következő állítást kellett igazolni: Egy kilenctagú társaságban mindenki pontosan öt másik embernek átad 100 Ft-ot. Bizonyítsuk be, hogy az ajándékozások után van két ember, akinek ugyanannyi forinttal változott a vagyona. (Arany Dániel-verseny 1990H) Igaz-e az is, hogy vagy van három ember, akinek ugyanannyi forinttal változott a vagyona, vagy van két-két ember, akiknek ugyanannyival változott a vagyona? b) Fogalmazzuk át gráfelméleti nyelvre az 1.1. feladatot és a fenti feladatot is! c) Hogyan általánosítható a feladat?
 

Feladat: 1.3.
Igaz-e a következő állítás: Egy n pontú, 3n élű egyszerű gráf vagy 6-reguláris, vagy van benne legalább hetedfokú pont?
 

Feladat: 1.4.
Hogyan általánosítható az 1.3. feladat állítása?
 

Feladat: 1.5.
Egy n=2k pontú egyszerű gráfban több, mint k2 él van. Bizonyítsuk be, hogy a) van benne háromszög; b) van benne négy hosszú kör. c) Bizonyítsuk be, hogy (izomorfiától eltekintve) egyetlen olyan 2k pontú, k2 élű gráf van, amelyben nincs háromszög: az a teljes páros gráf, amelynek mindkét osztályában k-k él van.
 

Feladat: 1.6.
* a) Bizonyítsuk be a részben rendezett halmazokra vonatkozó alábbi tételt:
Tétel. Ha egy részben rendezett halmazban a leghosszabb lánc n elemből áll, akkor a halmaz elemei beoszthatók n osztályba úgy, hogy az azonos osztályba tartozó elemek nem összehasonlíthatók. b) Bizonyítsuk be, hogy ha egy tranzitívan irányított gráfban a leghosszabb irányított útnak n pontja van, akkor a pontjai n színnel színezhetők úgy, hogy az egyszínűek között ne fusson él. (Egy irányított gráfot akkor és csak akkor nevezünk tranzitívnak, ha valahányszor ab → , bc → éle a gráfnak, mindig éle az ac → él is. L. a Bevezetőt.)
 

Feladat: 1.7.
Egy gyár hat különböző színű fonalból kétszínű kelmét gyárt. Minden szín legalább háromféle párosításban szerepel. Bizonyítandó, hogy kiválasztható háromféle kelme úgy, hogy mindegyik szín előfordul valamelyikben. (Kürschák verseny, 1957. l. [176])
 

Feladat: 1.8.
a) Bizonyítsuk be, hogy ha egy 2n pontú gráfban minden pont foka legalább n, akkor a gráf összefüggő. Csökkenthető-e itt a fokszámra tett kikötés? b) Igaz-e az is, hogy a gráf kétszeresen összefüggő?
 

Feladat: 1.9.
a) Egy húsztagú társaságban mindenki ismeri a társaság legalább 11 másik tagját (az ismeretségek kölcsönösek). Bizonyítsuk be, hogy van három ember, akik közül bármely kettő ismeri egymást. Mutassuk meg, hogy ha mindenki csak 10 másikat ismer, akkor ez már nem feltétlenül igaz. b) Hogyan általánosítható ez az állítás n tagú társaságra?
 

Feladat: 1.10.
Bizonyítsuk be, hogy a) ha egy húszpontú egyszerű gráfban bármely két pont fokszámának összege legalább 21, akkor van benne háromszög; b) ha egy n pontú egyszerű gráfban bármely két pont fokszámának összege legalább n+1, akkor van benne háromszög. c) Egy húsztagú társaságban minden ember megszámolja ismerőseit (az ismeretségek kölcsönösek). Azt tapasztalják, hogy ha bármely két ember összeadja az ismerőseinek a számát, akkor legalább 22 az eredmény. Bizonyítsuk be, hogy van négy ember, akik közül legfeljebb ketten vannak, akik nem ismerik egymást. d) Egy n pontú egyszerű gráfban bármely két pont fokszámának összege legalább n+2. Bizonyítsuk be, hogy van a gráfban olyan négypontú részgráf, amelyben legalább öt él van.
 

Feladat: 1.11.
[188] Adottak az a1 , a2 ,…, a3 n egész számok, és képezzük belőlük az összes ai - aj különbséget ( i<j). Bizonyítsuk be, hogy az így kapott 3n(3n-1)/2 különbség közül legfeljebb 3 n2 nem osztható hárommal. (Arany Dániel verseny, 1977/K, döntő)
 

Feladat: 1.12.
Próbáljuk meg az 1.11. feladatot gráfelméleti feladattá átfogalmazni: A 3n számnak egy 3n pontú gráf pontjait feleltetjük meg, két pontot akkor kötünk össze éllel, ha a megfelelő számok különbsége nem osztható hárommal. Azt kell belátnunk, hogy a gráfnak legfeljebb 3 n2 éle van. A kérdés az, hogy mit tudunk a gráfról, ami alapján be tudtuk látni a feladat állítását?
 

Feladat: 1.13.
Tekintsük azt a gráfot, amelynek csúcsai egy 8×8 sakktábla mezői, és kössünk össze két csúcsot, ha a megfelelő mezőknek a) van közös éle, b) van közös csúcsa. Mennyi az így kapott gráfok kromatikus száma?
 

Feladat: 1.14.
([4] 66. old.)* Tekintsük azt a gráfot, amelynek csúcsai egy 100×100 sakktábla mezői, és tekintsük egy lépésnek azt, amikor egyik mezőről átlépünk egy vele élben szomszédos mezőre. Kössünk össze két csúcsot, ha a megfelelő mezők egymástól pontosan két lépésnyire vannak. Mennyi ennek a gráfnak a kromatikus száma?
 

Feladat: 1.15.
([4] 66. old.) Egy gráf pontjai az 1,2,…,100 számok, két számot akkor köt össze él, ha közülük a nagyobbikat a kisebbikkel osztva kettőhatványt kapunk. Mennyi ennek a gráfnak a kromatikus száma?
 

Feladat: 1.16.
a) Egy gráfról tudjuk, hogy minden pont foka legalább három. Bizonyítsuk be, hogy négy színnel jól-színezhető. b) Hogyan általánosítható a)?
 

Feladat: 1.17.
Bizonyítsuk be, hogy egy gráf kromatikus száma pontosan akkor kettő, ha van benne él és minden köre páros.
 

Feladat: 1.18.
Hány színnel színezhető jól egy 2k+1 pontú kör?
 

Feladat: 1.19.
a) Hány lényegesen különböző három színű jólszínezése van egy ötpontú körnek? b) És egy hétpontú körnek? Két színezés akkor lényegesen különböző, ha a színek permutálásával és a gráf izomorfiájával nem vihetők egymásba.
 

Feladat: 1.20.
Bizonyítsuk be, hogy K.II.8.24. feladat gráfja nem tartalmaz három hosszú kört, és nem színezhető jól három színnel.
 

Feladat: 1.21.
Konstruáljunk olyan gráfot, amelyben a) nincsen négypontú teljes részgráf, mégsem színezhető jól négy színnel; * b) nincsen három pontú teljes részgráf mégsem színezhető jól négy színnel.
 

Feladat: 1.22.
* Egy sakkedzésen minden játékos legfeljebb k pontot szerzett (döntetlenért fél pont, győzelemért egy pont jár). Bizonyítsuk be, hogy akkor a) van olyan játékos, aki legfeljebb 2k mérkőzést játszott; b) a játékosok elhelyezhetők 2k+1 teremben úgy, hogy az azonos terembe kerülő játékosok még nem játszottak egymással. (Arany Dániel-verseny, 1990H)
 

Feladat: 1.23.
Bizonyítsuk be, hogy ha egy n pontú egyszerű gráfban több, mint n2 /4 él van, akkor legalább három szín kell a pontjai jólszínezéséhez.
 

Feladat: 1.24.
a) Egy 3n pontú gráfról tudjuk, hogy három színnel jólszínezhető. Bizonyítsuk be, hogy a komplementere jólszínezéséhez legalább n színre van szükség. b) Egy jn pontú gráfról tudjuk, hogy j színnel jólszínezhető. Bizonyítsuk be, hogy a komplementere jólszínezéséhez legalább n színre van szükség.
 

Feladat: 1.25.
* Bizonyítsuk be, hogy ha G egy n pontú egyszerű gráf, akkor G kromatikus számának és a komplementere kromatikus számának az összege legalább 2n. Fennállhat-e egyenlőség?
 

Feladat: 1.26.
Bizonyítsuk be, hogy ha G egy n pontú egyszerű gráf, akkor G kromatikus számának és a komplementere kromatikus számának az összege legfeljebb n+1. Fennállhat-e itt egyenlőség?
 

Feladat: 1.27.
* Egy százegy pontú teljes gráf éleit kiszíneztük úgy, hogy minden háromszög vagy egyszínű, vagy teljesen tarka (mind a három éle más színű). A színezéshez egynél több színt használtunk. Bizonyítsuk be, hogy ekkor legalább 12 színt használtunk.
 

Feladat: 1.28.
* Egy 1993 szögpontú teljes gráf minden élét kiszíneztük úgy, hogy semelyik csúcsba sem fut két azonos színű él. Bizonyítsuk be, hogy van 17 olyan pont, amelyek közül bármely kettőt különböző színű él köt össze.
 

Feladat: 1.29.
Bizonyítsuk be, hogy egy gráf élszínezési száma nem kisebb a gráfban fellépő maximális fokszámnál.
 

Feladat: 1.30.
Mennyi a Petersen-gráf a) kromatikus száma és b) élszínezési száma?
 

Feladat: 1.31.
* Egy véges egyszerű 3-reguláris gráf élei lényegében - azaz a színek permutálásától eltekintve - egyértelműen színezhetők ki 3 színnel. Bizonyítsuk be, hogy a gráfban van Hamilton-kör.
 

Feladat: 1.32.
Egy zsákban végtelen sok golyó van, mindegyik színe a három alapszín egyike: piros, kék vagy sárga. Bizonyítsuk be, hogy valamelyik színű golyóból végtelen sok van.
 

Feladat: 1.33.
Fogalmazzuk meg a skatulyaelvet végtelen halmazokra!
 

Feladat: 1.34.
a) Kijelöltünk a koordinátasík pozitív negyedsikjában végtelen sok téglalapot, mindegyiknek az origó az egyik csúcsa és egy-egy oldala a két tengelyen van, és az origóval szemközti csúcsa is rácspont. Bizonyítandó, hogy van a kijelöltek között kettő (különböző), amelyek közül az egyik tartalmazza a másikat. (Vö. Kürschák verseny, 1934. [176]) Mutassuk meg, hogy viszont tetszőlegesen sok ilyen téglalap megadható, amelyek közül egyik sem tartalmazza a másikat. b) Kijelöltünk végtelen sok egész számot azok közül, amelyeknek csak (legfeljebb) két prímosztójuk van: a 2 és a 3. Bizonyítandó, hogy e számok között van kettő, amelyek közül az egyik osztója a másiknak.
 

Feladat: 1.35.
* Adott k darab prím szám, p1 , p2 ,…, pk , továbbá adott végtelen sok szám, amelyek mindegyikének a prímosztói e k darab prím közül kerülnek ki. Bizonyítsuk be, hogy van a megadott számok között kettő, amelyek közül a kisebb osztója a nagyobbnak. (Dickson, vö. [173], 240. oldal.)
 

Feladat: 1.36.
Bizonyítsuk be a ,,végtelen Ramsey-tételt" a következő formájában:
Végtelen Ramsey-tétel/1: Bármely egyszerű végtelen gráfra igaz, hogy vagy maga a gráf, vagy a komplementere tartalmaz végtelen teljes részgráfot. Vagy másképp fogalmazva: bármely egyszerű végtelen gráf tartalmaz vagy teljes, vagy üres végtelen részgráfot. Ezt így jelöljük: ℵ0 →( ℵ0 , ℵ0 ).
 

Feladat: 1.37.
Bizonyítsuk be, hogy egy végtelen számsorozatban vagy van szigorúan monoton növekvő végtelen részsorozat, vagy van monoton csökkenő végtelen részsorozat.
 

Feladat: 1.38.
Az 1.36. feladatban kimondott Ramsey-tétel más megfogalmazásban azt állítja, hogy ha egy megszámlálható halmaz pontpárjait kiszínezzük két színnel, akkor van olyan megszámlálható részhalmaz, amelynek minden elempárja azonos színű. Vajon igaz-e ugyanez, ha nem a kételemű, hanem a háromelemű részhalmazokat színezzük? a) Próbáljuk meg ezt az állítást igazolni az 1.36. feladatban adott megoldással: b) Fogalmazzuk meg azt a segédállítást, amire szükségünk volna ahhoz, hogy a bizonyítást át tudjuk vinni erre az esetre is! c) Ha jól fogalmaztuk meg, be is fogjuk tudni bizonyítani, mert valójában egy már bizonyított állításról van szó.