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 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 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 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.
Nem kell túl sokáig keresgélnünk az interneten a fejtörő feladatok között ahhoz, hogy sík vagy tér kitöltésére vonatkozó feladványra bukkanjunk. Ezek egyik fajtája az, amikor néhány síkidom vagy test valamilyen keretben van elhelyezve úgy, hogy látszólag teljesen kitöltik azt, de van még külön egy további eleme a játéknak.
