Tait tételének bizonyítása

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.

1. Tartományszínezésből élszínezést

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