Hujter Bálint
A KöMaL 2025 szeptemberi számában (Tait tétele és a 3-reguláris gráfok – a B. 5403. feladat háttere, 346–350. oldal) 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.
A bizonyítást a könnyebb iránnyal kezdjük. Tegyük fel, hogy \(\displaystyle G\) tartományait sikerült jól kiszínezni 4 színnel (ezek legyenek: kék, piros, sárga és zöld). Belátjuk – ezt a színezést felhasználva –, hogy ekkor az éleket ki tudjuk jól színezni három színnel (lila, narancs, türkiz).
\(\displaystyle G\) minden éle két különböző színű tartomány között képez határvonalat (hiszen \(\displaystyle G\) hídélmentes). Az élek színeit az alapján határozzuk meg, hogy milyen színű tartományokat választanak el, az alábbi táblázat szerint:
Hogyan született a táblázat? A szabály az, hogy egy-egy sorban, illetve oszlopban 3 különböző színnek kell szerepelnie. Hiszen ha pl. a kék-piros és a kék-sárga tartományokat elválasztó élek ugyanolyan színűek lennének, akkor a gráf egy olyan csúcsánál, ahol egy kék, egy piros és egy sárga tartomány találkozik, két ugyanolyan színű él keletkezne. Könnyű meggondolni (ezt az Olvasóra bízzuk), hogy így minden csúcsban 3 különböző színű él fog találkozni. Egy példa a táblázat szerint színezett térképre:
1. ábra
Következik a nehezebb és izgalmasabb irány bizonyítása. (Ez az irány ad(na) lehetőséget a négyszín-tétel 3-élszínezéseken keresztül való bizonyítására.) Tegyük fel, hogy a 3-reguláris gráfunk élei már jól ki vannak színezve, gyártsuk le ebből a tartományok egy jó 4-színezését. Az előzőek ismeretében természetes ezt megpróbálni úgy csinálni, hogy a táblázatunkban rögzített szín-szabályok most is működjenek, azaz például egy kék és egy piros tartományt elválasztó határ mindig lila legyen.
Vegyük észre, hogy ha egy kiválasztott tartományt kedvünk szerint kiszínezünk (például a nem korlátos tartományt kékre), akkor így a táblázat már egyértelműen meghatározza a vele szomszédos tartományok színeit. Általában, ha egy még színezetlen tartományunk szomszédos egy már kiszínezett tartománnyal, akkor a táblázat alapján egyértelmű, hogy milyenre kell kiszínezni (ha például egy narancs színű él egyik oldala kék, akkor a másik oldalának muszáj sárgának lennie). Ilyen módon a gráf összes tartományát ki tudjuk színezni (amíg nincs az összes tartomány kiszínezve, addig mindig lesz olyan színezett tartomány, amely szomszédos egy színezetlennel).
De honnan tudhatjuk, hogy ez a tartományszínezés mindenhol jó lesz, azaz bármely két szomszédos tartomány különböző színű lesz a végén? Ennél is többet fogunk belátni: két szomszédos tartomány nem egyszerűen különböző színű lesz, hanem az őket elválasztó határvonal mindig épp a táblázat által diktált színű lesz, akkor is, ha nem az elválasztó él színét felhasználva színeztük ki a két tartományt.
A bizonyításhoz kössünk össze minden tartományt azzal a szomszédjával, amelyik alapján kiszíneztük. Jelöljünk ki minden tartományban egy belső pontot fővárosnak, ezek legyenek az összeköttetések végpontjai. Könnyen meggondolható, hogy így egy fagráfot kapunk, amelyet \(\displaystyle F^*\)-gal fogunk jelölni. A \(\displaystyle ^*\)-gal arra utalunk, hogy \(\displaystyle F^*\) a \(\displaystyle G\) síkbarajzolt gráf ún. duális gráfjának, \(\displaystyle G^*\)-nak az éleiből áll. (Így \(\displaystyle F^*\) a \(\displaystyle G^*\) egy feszítőfája.) Világos az is, hogy az összeköttetéseket be lehet úgy rajzolni, hogy:
2. ábra
Így \(\displaystyle F^*\) élei persze megfeleltethetők \(\displaystyle G\) egy-egy élének, és így beszélhetünk \(\displaystyle F^*\) éleinek színéről is. (Általában a \(\displaystyle G\) síkgráf és az ő \(\displaystyle G^*\) duálisának élei megfelelnek egymásnak. Ez a megfeleltetés ráadásul egy-egyértelmű ,,párbaállítás''.)
\(\displaystyle F^*\) minden éle azt a színt kapja, amilyen színű \(\displaystyle G\)-beli élet keresztez.
Legyen \(\displaystyle s\) és \(\displaystyle t\) két tetszőlegesen válaszott szomszédos tartomány \(\displaystyle G\)-ben. Ha \(\displaystyle F^*\)-ban él köti őket össze, akkor persze világos, hogy teljesülni fog a táblázat által diktált szabály, hiszen a később színezett tartományt éppen ez alapján színeztük ki.
És mi a helyzet, ha \(\displaystyle F^*\)-ban nem köti össze közvetlen él \(\displaystyle s\) és \(\displaystyle t\) fővárosát? Ilyenkor a fagráfok ismert tulajdonságai szerint \(\displaystyle F^*\)-ban egyértelműen létezik egy \(\displaystyle s\) és \(\displaystyle t\) fővárosát összekötő út, ezt jelöljük \(\displaystyle U^*\)-gal. Ezen út mentén kellene tudnunk végigkövetni a színváltásokat, és valahogy belátni, hogy az \(\displaystyle U^*\) két vége közötti ,,különbség'', azaz a táblázat által diktált határszín éppen az, aminek lennie kell.
Ahhoz, hogy egy utat végig tudjunk követni, számolnunk kellene tudni a színekkel, ehhez pedig valamilyen algebrai struktúrával kell ellátni őket. Ehhez vegyük azokat a 2-dimenziós vektorokat, amelyek mindkét koordinátája 0 vagy 1, és alkalmazzuk rájuk ezt a tömör jelölést: 00, 01, 10, 11. Ezeket koordinátánként (bitenként) modulo 2 számolva adjuk össze, vagyis az \(\displaystyle 1+0=0+1=1\) és \(\displaystyle 0+0=1+1=0\) szabály szerint. Ha a tartomány- és az élszíneket alkalmasan feleltetjük meg ezeknek a 2-bites objektumoknak, akkor igaz lesz, hogy a határoló él színe mindig az általa elválasztott tartományok színeinek összege. A táblázatunk tulajdonképpen a színek ,,összeadó-táblája'':
(Mint látható, az egyes vektorok tartományként vagy élként más-más színt jelentenek. A 01 például piros tartományt, de lila élet jelent.) Azért hasznos ez a megfeleltetés, mert ennek segítségével az \(\displaystyle s\) és \(\displaystyle t\) színének viszonyát jól meg tudjuk fogni. Ha ugyanis \(\displaystyle U^*\) élein végigmegyünk \(\displaystyle s\)-ből \(\displaystyle t\) felé, minden egyes \(\displaystyle e^*\) élen végigmenve éppen úgy változik meg a tartomány színe, mint ha az eddigi tartományszínhez hozzáadnánk \(\displaystyle e^*\) színét. Így az \(\displaystyle s\)-től \(\displaystyle t\)-ig történő változás éppen annyi, mint az \(\displaystyle U^*\) élei színeinek az összege. Azt kell tehát belátnunk, hogy ez az összeg megegyezik az \(\displaystyle s\) és \(\displaystyle t\) tartományokat elválasztó határvonal színével.
Kössük most össze \(\displaystyle s\) és \(\displaystyle t\) fővárosát egy új, közvetlen éllel (most is figyelve arra, hogy csak \(\displaystyle s\)-ben és \(\displaystyle t\)-ben haladjunk és a határukat csak egyszer, annak belső pontjában messük; továbbá \(\displaystyle F^*\) éleit se keresztezzük). Ez az új él az \(\displaystyle U^*\) úttal együtt egy gráfelméleti kört alkot, ezt jelöljük \(\displaystyle K^*\)-gal.
3. ábra
Állítás. A \(\displaystyle K^*\) éleinek színeit összeadva 00-t kapunk.
Bizonyítás. \(\displaystyle K^*\) élei nem keresztezik egymást, így a körnek lesz egyértelműen belseje, illetve külseje. A \(\displaystyle G\) csúcsai közül néhány csúcs belső, néhány csúcs külső lesz (a 2. ábrán a belső csúcsokat piros körökkel emeltük ki). Vegyük észre, hogy \(\displaystyle K^*\) élei a \(\displaystyle G\) élei közül éppen azoknak felelnek meg, amelyek egy belső és egy külső csúcsot kötnek össze.
Bármely csúcsra igaz, hogy a három ott találkozó él színének összege: \(\displaystyle 01+10+11 = 00\). Így ha az összes belső csúcsra összeadjuk az onnan kiinduló élek színét, akkor is \(\displaystyle 00\)-t kapunk. Ebben a \(\displaystyle \Sigma\) összegben kétszer szerepel minden olyan él, amely két belső csúcsot köt össze. De a modulo 2 összeadás tulajdonságai miatt, ha valamit saját magával adunk össze, akkor 00-t kapunk. Tehát \(\displaystyle \Sigma=00\) éppen megegyezik azon élek színeinek összegével, amelyek egy belső és egy külső csúcsot kötnek össze. Ez viszont megegyezik \(\displaystyle K^*\) élei színeinek összegével, hiszen \(\displaystyle K^*\) minden éle egy azonos színű – egy belső és egy külső csúcsot összekötő – \(\displaystyle G\)-beli élt metsz. \(\displaystyle \square\)
Tehát a \(\displaystyle K^*\) éleinek színeinek összege 00, ami éppen azt jelenti (a modulo 2 összeadás tulajdonságai miatt), hogy az \(\displaystyle U^*\) éleinek színeinek összege megegyezik az \(\displaystyle s\) és \(\displaystyle t\) tartományokat elválasztó határvonal színével, mivel ezen él színéhez csak a saját színét hozzáadva kaphattuk meg a 00-t. Ezt szerettük volna bizonyítani.
Egy szép ötlettel a nehezebb rész bizonyítása jóval rövidebben is elmondható. Tekintsük a 3-reguláris gráfunk éleinek egy jó színezését, ahol tehát minden csúcsban egy narancs, egy lila és egy türkiz él találkozik. Ebből kiindulva gyártjuk le a tartományaink 4-színezését. A tartományok lehetséges színeit most is két bittel fogjuk kódolni: korábban is alkalmazott módon 00 a kék, 01 a piros, 10 a sárga és 11 a zöld szín kódja.
Ideiglenesen felejtsük el a lila éleket, így maradnak a narancs és a türkiz élek, minden csúcsban egy-egy találkozik belőlük.
4. ábra
A narancs és a türkiz élek tehát egy 2-reguláris síkgráfot, azaz egy vagy több diszjunkt kört alkotnak. (Az ábrán bemutatott példán egyetlen kört alkotnak a narancs és türkiz élek. Akkor lehetne több kör, ha a lila élek egy része elvágó élhalmazt alkotnának, azaz a lila élek nélkül több összefüggőségi komponensre esne szét a gráf.)
Most minden kiszínezendő tartományára számoljuk meg, hogy hány ilyen narancs-türkiz körnek van a belsejében. Ha páros soknak, akkor a tartomány színének első bitje legyen 0; ha páratlan soknak, akkor pedig 1.
Ezután a narancs éleket felejtsük el ideiglenesen, így a lila-türkiz körök maradnak, amelyek egy másik diszjunkt körökből álló rendszert alkotnak. A tartományok színének második bitje legyen 0, ha páros sok körnek van a belsejében; illetve 1, ha páratlan soknak.
5. ábra
Könnyen meggondolható, hogy bármely két szomszédos tartomány színe különböző lesz. Ha narancs él választja el őket, akkor a színük első bitje különbözik. Ha lila él választja el őket, akkor a második bit különbözik. Egy türkiz él két oldalán pedig mindkét bit ellentétes lesz. Vagyis a 00, 01, 10 és 11 (kék, piros, sárga és zöld) színekkel sikerült úgy színeznünk a gráf tartományait, hogy a szomszédos tartományok mindig különböző színűek.
6. ábra
Megjegyzés. Tait az On the Colouring of Maps (Proceedings of the Royal Society of Edinburgh, Volume 10, 1880, pp. 501–503) című írásában azt látja be vázlatosan, hogy ha egy háromszögelt síkgráf élei ki vannak színezve úgy, hogy minden tartományt három különböző színű él határol (egy csúcsban több azonos színű él is találkozhat), akkor a csúcsait is ki tudjuk négy színnel színezni (úgy, hogy a szomszédos csúcsok különböző színűek). Tait fő ötlete az, hogy ha az egyik színű, pl. a lila éleket ideiglenesen egy-egy új csúccsal felosztjuk, akkor az így kapott gráf minden tartománya négy oldalú lesz. Belátható (ezt Tait sem részletezi), hogy az ilyen gráfok páros gráfok, azaz a csúcsaik két színnel színezhetők. Ha a lila élek visszaállítása után a narancs éleket osztjuk fel, akkor egy másféle 2 színnel való színezést kapunk. A kétféle kétszínű színezés összekombinálva a gráf csúcsainak olyan 4 színnel való színezését adja, melyben a szomszédos csúcsok mindig különböző színűek.
Ez a közvetlen bizonyítás lényegében Tait gondolatmenetének lefordítása a duális síkgráf nyelvére.
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 ...
A cikk egy feladatsorozaton keresztül meséli el, hogyan jött rá a szerző egy Erdős Pálhoz köthető, kisebb állításra. A cikk elsősorban azoknak lehet hasznos, akik már ismernek néhány, a gráfokkal kapcsolatos alapfogalmat – de ennyi elég is, a megértéséhez nincs szükség további gráfelméleti ismeretekre.
Még élénken él bennem az, ahogyan először találkoztam a gráfelmélettel. A Zalaegerszegi Zrínyi Miklós Gimnázium diákjaként néha betévedtem a könyvtárba, és a matekos részlegen nézegettem a könyveket. Ifjú kilencedikesként lenyűgözött a rengeteg könyv számomra érthetetlen címe, és csak reméltem, hogy talán valamikor majd megérthetem őket. Egyszer Andrásfai Béla Ismerkedés a gráfelmélettel című művét emeltem le a polcról, és nézegettem a már tizenöt évvel ezelőtt is nagyon réginek tűnő könyvet. (Az 1971-es kiadással találkoztam.)
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 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é!
A KöMaL 74. évfolyam 7. számában jelent meg a B. 5390. feladatnak két szép versenyzői megoldása. A feladat:
B. 5390. Léteznek-e olyan \(\displaystyle a_0\), \(\displaystyle a_1\), \(\displaystyle \ldots\), \(\displaystyle a_{n-1}\) páros egész számok, amelyekre az \(\displaystyle x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\) polinom osztható az \(\displaystyle x^2+x+1\) polinommal?
Vagyis – kicsit másképpen fogalmazva – a feladatban arra kerestük a választ, hogy van-e olyan \(\displaystyle s(x)\) polinom, amellyel megszorozva a \(\displaystyle q(x)=x^2+x+1\) polinomot olyan \(\displaystyle p(x)=x^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\) (nem azonosan nulla) egész együtthatós polinomot kapunk, amelynek ismeretlen együtthatói páros számok.
A legtöbb megoldó ,,visszaszorzással'' kereste az \(\displaystyle s(x)\) polinomot – és indirekt úton mutatta meg, hogy ilyen nincs.
Többen viszont polinomosztással oldották meg a feladatot. Mivel a kétféle hozzáállás lényegében ugyanazt a gondolatmenetet követi, ilyen megoldást nem közöltünk, ám a polinomosztásról, illetve a feladat polinomosztással történő megoldásáról érdemes néhány szót ejteni.
