A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. A megoldáshoz szükségünk lesz az út fogalmára. Az pontok utat alkotnak, ha , , , mindegyike éle a gráfnak. Az és pontokat az út kezdő- illetve végpontjának nevezzük. Ha az út végpontja megegyezik a út kezdőpontjával, akkor -vel jelöljük a két út összekapcsolásával keletkező utat. Ha a gráfban nincs Euler-kör, kész vagyunk; feltételezhetjük, hogy létezik egy Euler-kör. Mint ismeretes, ennek szükséges és elégséges feltétele, hogy a gráf összefüggő, és minden pont foka páros legyen.pl. Reiman István: A geometria és határterületei (321‐322. o.) vagy Hajnal‐Nemetz‐Pintér‐Urbán: Matematika (B fakt.) IV. oszt. 204‐206. o. (Tankönyvkiadó, 1982). A feladatot több esetre bontjuk attól függően, hogy a gráfban milyen fokszámú pontok vannak. I. eset: ha van legalább hatodfokú pont. Tekintsünk egy ilyen pontot, legyen ez , a foka . Az Euler-kör pontosan alkalommal megy át ezen a ponton, tehát létezik darab olyan út, amelynek kezdő- és végpontja is , továbbá ezek az utak minden élt pontosan egyszer tartalmaznak. Jelölje ezeket az utakat ,,; jelölje az megfordításával keletkező utat . Mivel a gráf egyszerű, ezek az utak legalább három élből állnak, és emiatt a megfordítással keletkező utak biztosan különböznek az eredetiektől. Az , utak tehát különbözők. Ekkor viszont fel tudunk sorolni legalább négy különböző Euler-kört: , , , . Az állítás tehát igaz. II. eset: ha van legalább két negyedfokú pont. Legyen és két negyedfokú pont. Az kör mindkét ponton kétszer megy át, ez kétféle sorrendben lehetséges: vagy . (A többi eset a kör pontjainak ciklikus cseréjével ebbe megy át.) A eseben az kört felbonthatjuk az , , , utakra, amelyeknek az indexükben megjelölt pontok a végpontjaik. Most is fel tudunk sorolni négy különböző Euler-kört: , , , . A esetben az kört az utakra bontjuk fel, amelyek közül és -ből -ba, és -ból -be halad. Ebben az esetben is létezik négy különböző Euler-kör: , , , . III. eset: ha a gráfban minden pont másodfokú. Ebben az esetben az Euler-kör egyértelmű, legfeljebb csak a körüljárás irányát választhatjuk meg. Az Euler-körök száma tehát egy. IV. eset: ha az egyik pont negyedfokú, a többi pedig (legfeljebb) másodfokú. Legyen a negyedfokú pont. Ezen az kör kétszer megy át, ezért a kört az és utakra (körökre) bontja. Tekintsünk egy Euler-kört. Ez szintén tartalmazza az és köröket, csupán ezek sorrendje és a körüljárásuk iránya lehet más. A kezdőpont és az irány megválasztásával elérhetjük, hogy először -t járja be ugyanolyan sorrendben, ezután pedig -t; itt kétféle körüljárás lehetséges. Ez pedig azt jelenti, hogy pontosan két Euler-kör van: és . Minden esetet megvizsgáltunk, az Euler-körök száma sohasem lehet pontosan három.
|