Hujter Bálint
A KöMaL 2022 őszi számaiban Tóthmérész Lilla egy alapos cikksorozatot ([1]) közölt a négyszín-sejtés történetéről, benne kiemelten Alfred Kempe 1879-ben közölt bizonyítási kísérletéről, amelyben Heawood 1890-ben találta csak meg a hibát.
A cikkben leírtakat érdemes kiegészíteni azzal, hogy 1880-ban egy másik, rendkívül érdekes bizonyítási kísérlet is történt. Egy Peter Guthrie Tait nevű skót matematikus ugyanis a következő szép állítást bizonyította, mindössze 1 évvel Kempe kísérlete után:
1. tétel (Tait tétele, 1880, [2]). A négyszín-sejtés ekvivalens azzal, hogy minden \(\displaystyle 3\)-reguláris, síkbarajzolható, hídélmentes gráf \(\displaystyle 3\)-élszínezhető.
A kimondott tétel több olyan gráfelméleti alapfogalommal dolgozik, amelyek közül néhánynak a jelentését érdemes tisztázni még írásunk elején.
Nem részletezzük külön a \(\displaystyle k\)-reguláris gráf, síkbarajzolható és síkbarajzolt gráf fogalmakat, mivel ezek a KöMaL-feladatokban is rendszeresen előfordulnak.
Egy gráfban hídélnek nevezünk egy élt, ha a kitörlésével a gráf valamelyik összefüggőségi komponense két részre szakad. Egy gráf hídélmentes, ha nincs benne hídél. Az összefüggő és hídélmentes gráfokat szokás 2-él-összefüggő gráfoknak is nevezni, mivel legalább 2 élet kell törölni ahhoz, hogy a gráf több komponensre essen szét. Általánosabban: egy gráfot \(\displaystyle k\)-él-összefüggőnek nevezünk, ha bármely \(\displaystyle k-1\) élének törlésével is összefüggő marad. \(\displaystyle k\)-csúcs-összefüggőnek vagy egyszerűen \(\displaystyle k\)-összefüggőnek nevezzük, ha bármely \(\displaystyle k-1\) csúcsának törlésével összefüggő marad.
Akkor nevezünk 3-élszínezhetőnek egy gráfot, ha az éleit ki lehet színezni 3 színnel úgy, hogy a szomszédos, azaz közös végponttal rendelkező élek különböző színűek. Ebben a cikkben, ha egy gráf csúcsainak, illetve éleinek színezéséről beszélünk, azon mindig olyan színezést értünk, amelyben a szomszédos csúcsok, illetve élek különböző színűek kell legyenek. Síkbarajzolt gráf esetén beszélhetünk tartományok színezéséről is, ilyenkor is azt értjük ezen, hogy az egymással szomszédos tartományok különböző színűek.
Egy gráf éleinek egy \(\displaystyle M\) részhalmaza teljes párosítás (vagy \(\displaystyle 1\)-faktor), ha a gráf minden csúcsából pontosan egy \(\displaystyle M\)-beli él indul. Érdemes meggondolni, hogy egy 3-reguláris gráf pontosan akkor 3-élszínezhető, ha az élhalmaza 3 diszjunkt teljes párosításra bontható.
A négyszín-sejtés állítása többféleképpen is kimondható a gráfok nyelvén. Az [1] elején a szerző részletesen elmagyarázza a szokásos absztrakciót, amellyel a színezendő térképre gráfként gondolhatunk: az országoknak egy-egy csúcsot feleltetünk meg, és a közös határral rendelkező országoknak megfelelő csúcsokat él köti össze. Ezen a nyelven a négyszín-sejtés állítása így hangzik: Minden síkbarajzolt (hurokélmentes) gráf csúcsainak létezik \(\displaystyle 4\) színnel való színezése.
De egy térképre gondolhatunk úgy is gráfként, hogy az országok közötti határok az élek, míg a csúcsok a térkép azon pontjainak felelnek meg, ahol három vagy több ország határai találkoznak. Az így kapott gráfnak a tartományait szeretnénk 4 színnel színezni úgy, hogy szomszédos (azaz közös határral rendelkező) tartományok különböző színűek legyenek. A gráfról feltehetjük, hogy hurokél és hídél sincs benne (egy hídél önmagával határos tartományt jelentene, vagyis a hídél mindkét oldala azonos színű lenne). Párhuzamos élek lehetnek a gráfban. A négyszín-sejtés ezen a nyelven így szól: Minden síkbarajzolt hurokél- és hídélmentes gráf tartományainak létezik \(\displaystyle 4\) színnel való színezése.
Ha nincs olyan pont a térképen, ahol háromnál több ország találkozik, akkor egy 3-reguláris gráfot kaptunk. Ha pedig van 3-nál nagyobb fokú pont, akkor használjuk az alábbi ábrán vázolt széthúzási műveletet.
Ezzel a színezés szempontjából csak nehezítettük a helyzetünket: az új gráf színezésekor \(\displaystyle A\)-nak és \(\displaystyle C\)-nek is muszáj különböző színt kapnia, pedig eredetileg lehettek volna azonos színűek. Vagyis ha az új gráfot ki lehet színezni négy színnel, akkor a széthúzás előttit is. Számunkra fontosabb, hogy az új gráf tartományainak egy jó színezése a régi gráfon is alkalmas színezést ad.
A széthúzási művelet ismételgetésével tetszőleges síkgráf tartományainak színezésének kérdését vissza tudjuk vezetni egy 3-reguláris síkgráf esetére. Nem triviális, de végiggondolható az is, hogy a széthúzási műveletet mindig el tudjuk úgy végezni, hogy ne képződjön hídél (akkor képződne hídél, ha \(\displaystyle A\) és \(\displaystyle C\) ugyanazon tartományhoz tartozna). A négyszín-sejtés bizonyításához tehát elegendő belátnunk, hogy 3-reguláris hídélmentes síkgráfok tartományait kiszínezhetjük. Így Tait tételéhez elég megoldanunk az alábbi, kézzelfoghatóbb feladatot.
1. feladat (Tait tételének átfogalmazása). Legyen \(\displaystyle G\) egy \(\displaystyle 3\)-reguláris, hídélmentes, síkbarajzolt gráf. Ekkor \(\displaystyle G\) tartományai akkor és csak akkor színezhetők \(\displaystyle 4\) színnel, ha élei \(\displaystyle 3\)-színezhetők.
A megoldás kifejezetten szép és egy középiskolás által kitalálható, ezért csak a novemberi KöMaL számban közöljük, ezzel is gondolkodásra biztatva Olvasóinkat.
Tait egy másik állítást is megfogalmazott, amellyel együtt már a négyszín-tétel bizonyítása is kész lenne.
Sejtés (Tait sejtése, 1880, [2]). Minden \(\displaystyle 3\)-reguláris, hídélmentes gráf \(\displaystyle 3\)-élszínezhető.
Tait utóbbi sejtése azonban hamis, a mai ismereteinkkel nem is olyan nehéz ellenpéldát találni. Sokunk kedvenc ellenpélda-gráfja, a Petersen-gráf itt kezdte hosszú karrierjét: Petersen egy 1898-as jegyzetében ([3]) le is írja, ahogy kifejezetten Tait sejtésére adott ellenpéldaként konstruálja a róla elnevezett 10-csúcsú gráfot.
Petersen rajza az 1898-as jegyzetből és a ma szokásos ábrázolás a Petersen-gráfról.
2. feladat. Bizonyítsuk be, hogy a Petersen-gráf nem \(\displaystyle 3\)-élszínezhető.
Megjegyzés. Tait tehát hibásan azt gondolta, hogy a síkbarajzolhatóságra nincs is szükség ahhoz, hogy 3-élszínezhető legyen egy 3-reguláris gráf. Vajon úgy igazzá válik a sejtés, ha a síkbarajzolhatóságot is megköveteljük? Igen, de ebben csak azért lehetünk biztosak, mert azóta belátták a négyszín-tételt. Márpedig Tait tétele működik abban az irányban is, amely az élszínezéseket vezeti vissza a tartományszínezésekre.
Petersen egyébként már korábban írt egy sokszor hivatkozott cikket ([4]) a 3-reguláris gráfokról, amelyben a legfontosabb tétel a következő:
2. tétel (Petersen, 1891, [4]). Minden \(\displaystyle 3\)-reguláris, hídélmentes gráfban van teljes párosítás.
Ennek bizonyítása sem elérhetetlen egy középiskolás matekversenyzőnek, de kevésbé szép és érdekes, mint Tait tételéé. Viszont egyszerű, jópofa feladat ellenpéldát keresni az állítás megfordítására.
3. feladat. Mutassunk olyan \(\displaystyle 3\)-reguláris gráfot, amelyben van teljes párosítás és van hídél is (azaz nem hídélmentes). Síkbarajzolható példa is van?
Tekintsük most át, hogy mi is derült ki eddig a 3-reguláris gráfok különböző fajtáiról.
\(\displaystyle {\bullet}\) Petersen tétele és a 3. feladat szerint a hídélmentesség erősebb megkötés, mint az, hogy van teljes párosítás.
Az elmondottak így foglalhatók össze egy tételben:
3. tétel. Minden (hurokélmentes) \(\displaystyle 3\)-reguláris gráfra teljesül, hogy:
(a) Ha \(\displaystyle 3\)-élszínezhető, akkor hídélmentes.
(b) Ha hídélmentes, akkor van benne teljes párosítás.
Ha a gráf síkbarajzolható, akkor (a) megfordítása is igaz, de a bizonyítása a négyszín-tétel bizonyításával egyenértékű.
Akinek van kedve gondolkodni a témához kapcsolódó, szép és nem túl nehéz (KöMaL B pontverseny szintű) feladatokon, azoknak ajánlunk még kettőt:
4. feladat (Kiskvant 81., Bergengóc példatár 90., [6]). Néhány évvel a Délnyugati Birodalom széthullása után a területén létrejött \(\displaystyle 16\) hercegség mindegyike \(\displaystyle 3\) másikkal barátságban élt, a többivel pedig ellenségeskedett. A hajdani birodalom szomszédságában található \(\displaystyle 8\) állam elhatározta, hogy segítséget nyújt a viszályokban tönkrement hercegségeknek, méghozzá mindegyik állam \(\displaystyle 2\) egymással barátkozó hercegségnek nyújt támogatást. Meg lehet-e szervezni minden esetben a segélyezést úgy, hogy mindegyik hercegség részesüljön belőle?
5. feladat. Bizonyítsuk be, hogy ha egy \(\displaystyle 3\)-reguláris gráfban van Hamilton-kör, élei \(\displaystyle 3\)-élszínezhető.
Az 5. feladat a 3. tétel egy kiegészítése. Mellesleg pedig az is következik belőle, hogy a Petersen-gráfban sincs Hamilton-kör.
További kapcsolódó problémák találhatók a Lovász-példatár ([5]) Kromatikus szám című fejezetének végén (9.50–9.57 feladatok).
Aki még szívesen olvasna tovább a témában, annak ajánlunk két angol nyelvű wikipédia-oldalt, melyek a kérdéskör egy-egy lehetséges továbbgondolásához, máig nyitott kutatási kérdésekhez nyitnak kaput.
[1] Tóthmérész Lilla: Négyszín-sejtés I. A sejtés születése és egy bizonyítási kísérlet, KöMaL 2022. szeptember.
[2] P. G. Tait, Remarks on the Colouring of Maps, Proceedings of the Royal Society of Edinburgh, Vol. 10, No. 4, 1880, pp. 501–503.
[3] Petersen, Julius (1898), Sur le théorème de Tait, L'Intermédiaire des Mathématiciens, 5: 225–227.
[4] Petersen, Julius (1891), Die Theorie der regulären graphs, Acta Mathematica, 15: 193–220. (Szabadon letölthető a projecteuclid.org oldalról.)
[5] Lovász László: Kombinatorikai problémák és feladatok, Typotex, Budapest, 2008.
[6] Bergengóc példatár, Typotex, Budapest, 1999.
[7] A cikkben tárgyalt kérdések jelentős részével Király Zoltán Gráfelmélet gyakorlat c. óráján (ELTE matematikus MSc) találkoztam először 2011 tavaszán, ekkor kezdődött a téma iránti érdeklődésem.
A KöMaL 2025 szeptemberi számában (Tait tétele és a 3-reguláris gráfok – a B. 5403. feladat háttere) kimondtuk Tait alábbi tételét.
Tétel (Tait tétele). Legyen \(\displaystyle G\) egy 3-reguláris, hídélmentes, síkbarajzolt gráf. Ekkor \(\displaystyle G\) tartományai \(\displaystyle 4\)-színezhetők akkor és csak akkor, ha élei \(\displaystyle 3\)-színezhetők.
A tételben \(\displaystyle k\)-színezésen olyan színezést értünk, amely \(\displaystyle k\)-féle színt használ, és az egymással szomszédos tartományok (illetve élszínezés esetén az egy csúcsban találkozó élek) mindig különböző színűek.
A szeptemberi számba nem került be a tétel bizonyítása (azzal a céllal, hogy akinek van kedve, gondolkodhasson rajta), ezt most pótoljuk.
Azok is figyelmesen olvassák el a Versenykiírást, akik tavaly már részt vettek versenyünkben.
Idén is matematikából, fizikából és informatikából indítunk versenyeket. Egyénileg, illetve csapatban is lehet versenyezni, a versenyek 9 hónapon keresztül, 2025. szeptemberétől 2026. június elejéig tartanak. Minden hónapban új feladatokat tűzünk ki, és a megoldásokat a következő hónap elejéig küldheted be. A verseny végeredményét a 2026. szeptemberi számunkban hirdetjük ki. A díjakat jövő ősszel, a KöMaL Ifjúsági Ankéton adjuk át.
A KöMaL egy példányának ára 2025. szeptembertől 1600 Ft, előfizetése 1 évre 12500 Ft – BJMT tagoknak 12000 Ft.
Megrendelem
A Hanoi tornyai egy olyan feladvány, amelyben három függőleges pálcán van \(\displaystyle n\) db, különböző külső átmérőjű lyukas korong [2]. A hagyományos kiindulási állapotban a bal szélső pálcán van az összes korong, fentről lefelé növekvő méretben, a célállapot pedig ugyanez a korongpiramis, csak a jobb szélső pálcán. Két egyszerű szabályt kell betartani: minden lépésben valamelyik pálca legfelső korongját tehetjük egy másik pálca tetejére, továbbá semelyik korongot sem szabad nála kisebb korongra tenni. Igazolható, hogy a szükséges lépésszám \(\displaystyle 2^n - 1\), azaz minden egyes korong hozzáadásával lényegében megduplázódik.
Legutóbb szeptemberi számunkban foglalkoztunk bújócska típusú ördöglakatokkal. Elkészítésre ajánlottunk olvasóinknak egy pálcás változatot, ahol a ,,szokásos'' trükk nem működik, mivel az átbújtatás után (lásd ábra) a pálca nem fér át a hurkon a zsinór rövidsége miatt. Azonban vegyük észre, hogy ebben az átbújtatott állapotban valójában annyi a célunk, hogy a hurok a dupla zsinór másik oldalára kerüljön. Ezt úgy is elérhetjük, ha a téglatest formájú ,,alapot'' bújtatjuk át a hurkon.
Ha egy négyzetet a két átlójával felosztunk négy háromszögre, majd ezeket kiszínezzük három színnel az összes lehetséges módon, akkor megkapjuk a négyzetes színdominókat.
A színdominókat először a múlt század elején írta le Percy Alexander MacMahon, a kalandos életű matematikus. Ő rögtön megadott több nehéz feladatot is hozzájuk.
A KöMaL kiadásának, a versenyek teljes lebonyolításának, díjazásának és a díjkiosztóval egybekötött Ifjúsági Ankétok szervezésének költségeit 2007 óta a MATFUND Középiskolai Matematikai és Fizikai Alapítvány fizeti.
Kérjük, személyi jövedelemadója 1%-ának felajánlásával álljon a több, mint 125 éve alapított Középiskolai Matematikai és Fizikai Lapok mellé!
Nem kell túl sokáig keresgélnünk az interneten a fejtörő feladatok között ahhoz, hogy sík vagy tér kitöltésére vonatkozó feladványra bukkanjunk. Ezek egyik fajtája az, amikor néhány síkidom vagy test valamilyen keretben van elhelyezve úgy, hogy látszólag teljesen kitöltik azt, de van még külön egy további eleme a játéknak.
A Középiskolai Matematikai és Fizikai Lapok évről évre bővülő számú évfolyama – jelenleg 1893–1901-ig és 1965 és 2019 között – többféle szempont szerint kereshető, és a kiválogatott feladatok, cikkek kinyomtathatóak. Az összetett kereséssel igazi kincsestárban kutathatnak ingyenesen az olvasók: lehet keresni cikkekben és feladatokban többek között cím, szöveg, kategória (pl. versenyek), témakör és név alapján.
Az ELTE-n végzett matematikusokat nemcsak a kutatóintézetek, egyetemek várják, hanem számos cég is, igen jó fizetéssel. Esetleg még nem döntöttél, de leginkább matematikából folytatnál felsőfokú tanulmányokat? Minderre kitűnő lehetőség nyílik az ország egyik legnagyobb múltú egyetemén, az Eötvös Loránd Tudományegyetem Természettudományi Karán, ahol világhírű professzoroktól és lelkes, közvetlen fiatal oktatóktól tanulhatsz. Pezsgő diákélet vár rád az ELTE korszerű számítógépparkkal felszerelt, a KöMaL szerkesztőségének is otthont adó modern lágymányosi épületegyüttesében.
