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) 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 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 ...
Paulovics Zoltá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.)
