Pósa-tétel

A Dirac-tételen szeretnénk túllépni, a fokszámokra vonatkozó gyengébb feltételek mellett szeretnénk Hamilton-kör létezését biztosítani.

Feltesszük, hogy a d₁ <₌ d₂ <₌ d₃ <₌ ... <₌ d_n-2 <₌ d_n-1 <₌ d_n fokszámok rendezett sorozatában d₁ >₌ 2, d₂ >₌ 3, d₃ >₌ 4, ... d_i >₌ i+1, egészen addig, amíg a fokszámra vonatkozó alsó becslés eléri |V(G)|/2-t. Ha i+1 meghaladja |V(G)|/2-t, akkor d_i-re vonatkozó alsó becslés |V(G)|/2 lesz, azaz a Dirac-tétel feltétele. Ezen feltételt nevezzük Pósa-feltételnek. Legyen v_i az a csúcs, amely a fokszámsorozat i-edik elemét adja, azaz d(v_i)=d_i. A csúcsok közt nagyobb fokszám nagyobb index-szel jár, nagyobb index legalább akkora fokszámot jelent (azaz az index növelésével elképzelhetõ, hogy a fokszám nem nõ, hanem marad).

Kezdjük el Dirac tételének bizonyításá. legyeb P egy nem Hamilton-út. Legyen v a végpontja. Elképzelhetõ, hogy v=v₁ és d₁=2. Így P végpontja lehet nagyon kis fokú, azaz P-nek (ha mohó módon nem folytatható) csak két csavart változata van (egy valódi csavarása). Így a csavart változatok végponthalmaza kicsi. Ez nem garantálja olyan csavart végpont létét, amleynek van P-n kívüli szomszédja. Ennek ellenére mégis tudunk valamilyen ``elõrelépést'' garantálni. Ha v=v_i és i<₌, akkor v-nek legalább i+1 szomszédja van, azaz (ha mohó módon nem folytatható) legalább i+1 elemû a csavart P-k végponthalmaza, amelynek így kell olyan elmének lennie, amelynek index meghaladja i-t. Kaptuk a következõ állítást.

Lemma: Legyen P egy tetszõleges út egy egyszerû gráfban, amely teljesíti a Pósa-feltételt. Ekkor P-bõl elindulva csavarások ismételgetesével elérhetjük, hogy olyan Q-hoz jussunk, amelyre a következõ két feltétel valamelyike teljesül
(i) mohó módon növelhetõ,
(ii) végpontjának foka legalább |V(G)|/2 és összes szomszédja Q-ra esik.

Egy út megfordítható és korábbi végpontja kezdõpontként szolgálhat, illetve korábbi kezdõpontja az új végpont lesz. Ennek megfelelõen akorábbi gondolatunkat újból megismételhetjük, megduplázhatjuk. Így kapjuk a következõ lemmát.

Lemma: Legyen P egy tetszõleges út egy egyszerû gráfban, amely teljesíti a Pósa-feltételt. Ekkor P-bõl elindulva csavarások ismételgetesével, megfordítással, majd ismét csavarások ismételgetesével elérhetjük, hogy olyan Q-hoz jussunk, amelyre a következõ két feltétel valamelyike teljesül
(i) mohó módon növelhetõ,
(ii) mindkét végpontjának foka legalább |V(G)|/2 és mindkét végpont összes szomszédja Q-ra esik.

A fenti ``szerencsétlen'' (ii) esetben, ahogy Dirac-tételnél Hamilton-utat Hamilton-körré zártuk Q itt is körré zárható.

Definíció: Legyen P egy legalább kettõ hosszú út. Ha P két végpontja összekötött, akkor az összekötõ él P-vel együtt egy kört ad, amelyet P triviális bezárásának nevezünk.

Decfiníció: Legyen P egy legalább kettõ hosszú uv út. Ha P v végpontjának egy P-re esõ szomszédját P csavarására használjuk, amely csavart út végpontja összekötött u-val (P és a csavart P kezdõpontja), akkor a csavart P-t zárhatjuk be egy körre. Az így kapott kört P csavart bezárásának nevezzük (amely fogalaom magában foglalja a triviális bezárás fogalmát).

Ha egy P út mindkét végpontjának legalább |V|/2 (elég lenne azt mondanunk, hogy legalább |V(P)|/2 darab) szomszédja esik P-re, akkor P csavart módon bezárható. Valóban az uv út v végpontjának P-re esõ szomszédai mind egy csavaráshoz vezetnek, amely utak véponthalmaza egy legalább |V|/2 elemszámú U ponthalmaz. u P-re esõ szomszédai is legalább |V|/2 elemû S halmazt alkotnak. U és S V(P)-{u} részhalmazai így lesz közös pontjuk, ami állításunk igazolásához vezet. Összegezve:

Lemma: Legyen P egy tetszõleges út egy egyszerû gráfban, amely teljesíti a Pósa-feltételt. Ekkor P-bõl elindulva csavarások ismételgetesével, megfordítással, majd ismét csavarások ismételgetesével elérhetjük, hogy olyan Q-hoz jussunk, amelyre a következõ két feltétel valamelyike teljesül
(i) mohó módon növelhetõ,
(ii) csavart módon bezárható.

A Q út körré alakítása azért jó, mert minden u pontjára teljesül, hogy az egyik erre illeszkedõ él elhagyásával olyan uttá tehetõ, amely végpontja a kinézett csúcs. Azaz egy sokkal hatékonyabb eljárás mint a csavarás, amely csak fokszámnyi sok alternatív végponthoz vezet (szemben Q összes pontjával). Ha V(Q) (ami ugyanaz mint a kiinduló P ponthalmaza) valamely pontjának van V(Q)-n kívüli szomszédja, akkor Q növelhetõ.

Definíció: Egy P út bezárásos növelése alatt azt értjük, hogy P-t csvart módon körré alakítjuk (bezárjuk), a kör egy élet elhagyva egy utat nyerünk, amelyet mohó módon meghosszabítunk.

A bezárásos növelés biztosan fennáll, ha G gráfunk összefüggõ és utunk ponthalmaza nem a teljes ponthalmaz. A Pósa-fétetel garantálja az összefüggõséget. Valóban. tegyük fel, hogy G nem öszefüggõ. Legyen C a legkisebb pontszámú komponense. Legyen C pontszáma i<₌|V|/2. Ekkor C összes pontja (i darab csúcs) olyan, hogy fokszáma kisebb legyen mint i. Ezt kizárja a Pósa-feltétel, ami az összefüggõséget igazolja. Így kaptuk a következõt.

Lemma: Legyen P egy tetszõleges út egy egyszerû gráfban, amely teljesíti a Pósa-feltételt. Ha P nem Hamilton-út, akkor P-bõl elindulva csavarások ismételgetesével, megfordítással, majd ismét csavarások ismételgetesével elérhetjük, hogy olyan Q-hoz jussunk, amelyre a következõ két feltétel valamelyike teljesül
(i) mohó módon növelhetõ,
(ii) bezárásos módon nmövelhetõ.

Következmény: Egy Pósa-feltételt teljesítõ egyszerû gráfban van Hamilton-út. Ez a Hamilton-út egy korábbi lemma alapján körré zárható. Így kaptuk a következõ tételt.

Tétel (Pósa Lajos tétele): Egy Pósa-feltételt teljesítõ egyszerû gráfban van Hamilton-kör.

Pósa Lajos egy csodagyerekként indult matematikus. Elsõ matematikus éveirõl õ maga számol be a Természet Világa folyóiratban. Történetérõl az interneten is olvashatunk.