Utak és körök

Egy összefüggő gráfban pontosan akkor létezik Euler-kör (olyan zárt vonal, amely a gráf minden élét pontosan egyszer tartalmazza), ha a gráf minden csúcsának foka páros szám. Ezt az állítást Euler bizonyította a königsbergi hidak problémájának megoldásakor.

Nem tartalmaz. Egy gráfban akkor és csak akkor van Euler-vonal (amely nem zárt kör), ha pontosan két páratlan fokú csúcsa van. Euler-körhöz pedig az összes csúcsnak páros fokúnak kell lennie. Mivel ebben a gráfban 8 darab páratlan fokú csúcs található, a gráf sem Euler-vonalat, sem Euler-kört nem tartalmaz.

A $K_{3,3}$ gráf 6 csúccsal rendelkezik, melyek mindegyike 3-as fokszámú (tehát páratlan). Ahhoz, hogy Euler-kör jöjjön létre, minden csúcs fokszámát párosra kell változtatni. Minden hozzáadott él pontosan két csúcs fokszámát növeli meg eggyel. Ahhoz, hogy mind a 6 páratlan fokú csúcs páros fokúvá váljon, minimálisan 3 élt kell behúznunk, amelyek páronként összekötik ezeket a csúcsokat. Tehát legalább 3 él hozzáadása szükséges.

Ha egy összefüggő gráfnak pontosan két páratlan fokú csúcsa van, akkor a gráf bejárható egy Euler-vonallal. A bejárásnak kötelezően az egyik páratlan fokú csúcsból kell indulnia, és a másik páratlan fokú csúcsban fog véget érni. Emiatt az ilyen vonal sohasem lehet zárt (azaz Euler-kör).

A Petersen-gráf arról nevezetes a gráfelméletben, hogy számos érdekes ellenpéldát szolgáltat. Bár tartalmaz Hamilton-utat (olyan utat, amely minden csúcsot pontosan egyszer érint), Hamilton-kört nem tartalmaz.

A Dirac-tétel kimondja: ha egy $n$ csúcsú ($n \ge 3$) egyszerű gráfban minden csúcs foka legalább $\frac{n}{2}$, akkor a gráfban biztosan létezik Hamilton-kör. Fontos megjegyezni, hogy ez egy elégséges, de nem szükséges feltétel.

Igen, lehetséges. Ezt a feladatot a gráfelméletben "zárt huszárkörút" problémaként ismerjük, ami valójában egy Hamilton-kör keresését jelenti egy olyan gráfban, ahol a csúcsok a mezők, az élek pedig a szabályos huszárlépéseket jelölik. Schwenk tétele bizonyítja, hogy a hagyományos 8x8-as táblán létezik ilyen megoldás.

Egy Euler-kör minden élt pontosan egyszer tartalmaz. Ha egy gráfnak lenne elvágó éle (hídja), amely a gráfot két különálló komponensre osztja, akkor az Euler-kör bejárása során, miután ezen az élen átmentünk az egyik komponensből a másikba, soha nem tudnánk visszatérni az eredeti komponensbe anélkül, hogy ne használnánk újra ugyanazt az elvágó élt. Ez viszont ellentmondana az Euler-kör definíciójának (minden él pontosan egyszeri bejárása).

A $K_n$ teljes gráf minden csúcsa össze van kötve minden másik csúccsal, így minden csúcs fokszáma $n-1$. Az Euler-kör létezésének feltétele, hogy minden csúcs foka páros legyen. Az $n-1$ pontosan akkor páros szám, ha $n$ páratlan. Mivel gráfról beszélünk, $n \ge 3$ páratlan számokra (pl. 3, 5, 7) tartalmaz a gráf Euler-kört.

Egy összefüggő fa gráfnak csak akkor lehet Euler-vonala, ha a benne lévő páratlan fokú csúcsok száma pontosan nulla vagy kettő. Mivel a fákban nincsenek körök, és minden fának van legalább két elsőfokú (tehát páratlan) csúcsa (levele), nulla páratlan csúcs nem lehetséges. A pontosan két páratlan csúcs viszont azt jelenti, hogy a gráf kizárólag elsőfokú és másodfokú csúcsokat tartalmaz. Ez szerkezetileg azt jelenti, hogy a fa egyetlen egyenes "útgráf".

Egy olyan utat, amely a gráf minden csúcsát pontosan egyszer érinti, Hamilton-útnak nevezünk. Érdekesség, hogy William Rowan Hamilton éppen a dodekaéder gráfján keresett Hamilton-köröket egy általa "Icosian Game" néven piacra dobott társasjátékban 1857-ben.

Nem igaz. Egy egyszerű ellenpélda a $K_{2,4}$ teljes páros gráf. A két színosztály elemszáma 2 és 4, tehát nem egyeznek meg. Ugyanakkor a 2 elemű osztályban lévő csúcsok foka 4, a 4 elemű osztályban lévő csúcsok foka pedig 2. Mivel minden csúcs foka páros szám, a gráf tartalmaz Euler-kört.

A $n$ darab csúcs sorbarendezéseinek száma $n!$. Mivel a kör egy zárt struktúra, a kezdőcsúcs megválasztása nem számít, így osztanunk kell $n$-nel, ami az $(n-1)!$ körmutációt adja. Mivel az irányítást (jobbra vagy balra haladunk a körön) sem különböztetjük meg, ezt még el kell osztanunk 2-vel. Így a lehetséges Hamilton-körök száma: $\frac{(n-1)!}{2}$.

Számoljuk össze a páratlan fokú csúcsokat. A megadott sorozatban a 3, 3, 3, 5 értékek páratlanok. Ez pontosan 4 darab páratlan fokú csúcsot jelent. Mivel Euler-vonal csak abban az esetben létezhet, ha a gráfban pontosan 0 vagy 2 darab páratlan fokú csúcs van, ebben a gráfban biztosan nem létezik Euler-vonal.

A Hamilton-kör a gráf minden csúcsát pontosan egyszer érinti, majd visszatér a kiindulópontba. Mivel a páros gráf élei mindig az egyik színosztályból a másikba vezetnek, a kör mentén az "színek" felváltva kell, hogy kövessék egymást. Ez egy zárt láncolat esetén csak akkor lehetséges, ha a két színosztályban ugyanannyi csúcs van. Tehát $n = m$ szükséges. Továbbá a kör kialakításához legalább 2-2 csúcsra van szükség, így a feltétel: $n = m \ge 2$.

Mivel a gráf 4-reguláris, minden csúcsának foka páros (4), tehát kezdetben tartalmaz Euler-kört. Egyetlen él eltávolítása pontosan két csúcs fokszámát csökkenti eggyel. Így ezen a két csúcson a fokszám 3-ra (páratlanra) változik. Mivel egy Euler-körhöz minden csúcs fokának párosnak kell lennie, már 1 él eltávolítása is elegendő ahhoz, hogy az Euler-kör megszűnjön (bár Euler-vonal ekkor még biztosan lesz benne).

Több ilyen gráf is létezik, de a legegyszerűbb példák az $n \ge 5$ csúcsú körgráfok, például a $C_6$ hatszög gráf. A $C_6$ egyértelműen tartalmaz Hamilton-kört (hiszen maga az egész gráf egy kör). Ugyanakkor minden csúcsának foka csupán 2, ami sokkal kisebb, mint a Dirac-tétel által megkövetelt $\frac{n}{2} = \frac{6}{2} = 3$. Ez jól demonstrálja, hogy a feltétel teljesülése nélkül is létezhet Hamilton-kör.

Igen, igaz. Egy körmérkőzéses bajnokságot úgynevezett bajnoksággráffal (tournament) modellezünk, amely egy olyan irányított gráf, ahol bármely két csúcs között pontosan egy irányított él fut. Rédei László tétele kimondja, hogy minden bajnoksággráfban létezik legalább egy irányított Hamilton-út.

Igen, lehetséges. Ha a gráf az 5 csúcsú körgráf (azaz a $C_5$), akkor ebben az egyetlen lehetséges módon mehetünk körbe a csúcsokon (ha a kezdőpontot és a bejárás irányát nem különböztetjük meg). Tehát a gráfnak pontosan 1 darab Hamilton-köre van.

Nem következik. Bár a feltétel garantálja, hogy a gráf összefüggő és van benne Hamilton-kör, az Euler-körhöz az is elengedhetetlen, hogy kivétel nélkül minden csúcs foka páros legyen. A feltétel ("legalább 50") megengedi, hogy legyenek például 51-es, azaz páratlan fokszámú csúcsok is. Amint akár csak egyetlen páratlan fokú csúcs is van a gráfban, az Euler-kör nem jöhet létre.