Tait tétele és a 3-reguláris gráfok – a B. 5403. feladat háttere

Hujter Bálint

Bevezető, fogalmak

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ó.

Tait és a négyszín-sejtés

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\)-él­színez­hető.

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.

A 3-reguláris gráfok világa

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.

• riviális, hogy a 3-élszínezhetőség is erősebb, mint a teljes párosítás létezése.
• És vajon mi a viszony a 3-élszínezhetőség és a hídélmentesség között?
• Egyrészt a Petersen-gráf hídélmentes, de nem 3-élszínezhető. Tait tétele ugyanakkor a négyszín-tétellel együtt azt implikálja, hogy a síkbarajzolható 3-reguláris gráfok között minden hídélmentes gráf 3-élszínezhető is.
• És mi a helyezet a másik iránnyal? Nos, éppen ez volt a kérdés a B.5403. feladatban, kicsit általánosabban kérdezve.

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ű.

További gondolkodni- és olvasnivaló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.

• Tait's conjecture https://en.wikipedia.org/wiki/Tait%27s_conjecture
• Snark (graph theory) https://en.wikipedia.org/wiki/Snark_(graph_theory)

Forrásjegyzék

[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.