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. Aki megoldja az egymásra épülő feladatokat, az joggal állíthatja, hogy ő is bebizonyította ezt a tételt!
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.)
Egy teljesen új világ tárult fel előttem. Nem sokkal később találtam más, újabb könyveket is, amelyeket nyáron olvasgatva elmerülhettem a témában. Andrásfai Béla könyvének ez a feladata valamiért nagyon megfogott:
1. feladat. Bizonyítsuk be, hogy bármely tetszőlegesen irányított teljes gráfban van olyan pont, amelyből a gráf bármely más pontja elérhető 2-nél nem hosszabb irányított úttal. ([3] 58. o. 16. feladat)
Sokáig gondolkoztam rajta, de nem tudtam megoldani, és végül feladtam. Megnéztem a megoldás első gondolatát, megértettem, és a homlokomra csaptam: „Ó, ez milyen egyszerű!” Kicsit csalódott voltam, hogy nem jöttem rá magamtól, de kárpótolt a megoldás szépsége: annyira egyszerű és frappáns volt!
Aki nem ismeri a feladat megoldását, és van kedve gondolkodni rajta, az még ne nézze meg a máris következő bizonyítást.
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 ...
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 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.
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é!
