Ore-tétel

A matematika, azon belül a gráfelmélet területén az 1960-ban Øystein Ore norvég matematikus által bizonyított Ore-tétel elégséges feltételt ad gráfban Hamilton-kör létezésére, lényegében azt állítja, hogy elegendően nagy számú éllel rendelkező gráfnak mindig van Hamilton-köre. Specifikusan a tétel a nem szomszédos csúcspárok fokszámainak összegeit vizsgálja: ha bármely nem szomszédos csúcspár fokszámösszege eléri a gráf csúcsainak számát, akkor a gráfnak van Hamilton-köre.

A tétel megfogalmazása

Ore-tétel (1961): Ha $G$ egy $n\ge 3$ csúcsú olyan egyszerű gráf, amire teljesül, hogy ha $x,y\in V(G)$ nem alkotnak élt (összekötetlenek), és ekkor $d(x)+d(y)\ge n$, akkor $G$-ben van Hamilton-kör.

Bizonyítás

Tegyük fel indirekt, hogy a gráf kielégíti a feltételt, de nincsen benne Hamilton-kör. Ez az ellenpélda gráfunk legyen $G^{\text{'}}$. Húzzunk be $G^{\text{'}}$-be további éleket úgy, hogy az új gráf is ellenpélda legyen (továbbra sincs benne Hamilton-kör). Így kapunk egy $G$ gráfot, ami továbbra is ellenpélda, hisz új élek behúzásával "rossz pontpárt" nem lehet létrehozni, de ha még egy élet akárhogyan behúzunk, akkor már tartalmaz a gráf Hamilton-kört. Biztosan van két olyan pont, hogy $\{x,y\}\notin E(G)$, hiszen egy $n$ csúcsú teljes gráfban van Hamilton-kör. Ekkor viszont a $G\cup \{x,y\}$ gráfban van Hamilton-kör, tehát $G$-ben van Hamilton-út. Legyenek a $P$ Hamilton-út csúcsai: $v_1,v_2,...,v_n$, és $v_1=x$ és $v_n=y$. Ha $x$ szomszédos a $P$ út valamely $v_{i+1}$ pontjával, akkor $y$ nem lehet összekötve $v_i$-vel, mert ez esetben ($v_1,v_2,...,v_i,v_n,v_{n-1},...,v_{i+1},v_1$) egy Hamilton-kör lenne.

A szaggatottal jelölt él nem lehet éle a gráfnak, mert így egy Hamilton-kört kapnánk

Így tehát

$y$

nem lehet összekötve legalább

$d(x)$

darab ponttal, ezért

$d(y)\le n-1-d(x)$$d(y)+d(x)\le n-1$

ami viszont ellentmondás, hiszen

$d(y)+d(x)\ge n$

volt feltéve.

Megjegyzések

• A fenti feltétel tehát a szomszédos pontpárok fokszámösszegéről nem mond semmit. Ki lehet mondani a tételt kissé más megfogalmazásban is: Ha az $n$ csúcsú $G$ gráfban nincs olyan $x,y\in V(G)$ pontpár, amelyre $d(x)+d(y)<n$ és $\{x,y\}\notin E(G)$, akkor $G$-ben van Hamilton-kör.
• A tétel nevét Øystein Ore norvég matematikusról kapta.
• Ez tehát egy elégséges – de nem szükséges – feltétel Hamilton-kör létezésére.

A Pósa-tétel és az Ore-tétel kapcsolata

Állítás

Pósa-tétel $\Rightarrow$ Ore-tétel

Bizonyítás

Azt kell tehát igazolnunk, hogy a Pósa-tétel egy gyengébb feltételből jut ugyanarra a következtetésre (hogy a gráfban van Hamilton-kör), azaz, hogy a Pósa-tételben szereplő feltétel mindig teljesül, ha az Ore-tételbeli feltétel teljesül.

Tegyük fel indirekt, hogy ez nem igaz, azaz létezik olyan $G$ $n$ csúcsú egyszerű gráf, hogy teljesül rá az Ore-feltétel, de a Pósa-féle nem: $\mathrm{\exists }k<\frac{n}{2}$, amire $d_k\le k$. Rögzítsünk le egy ilyen $k$-t! Mivel $d_1\le ...\le d_k\le k<\frac{n}{2}$, így a $k$ darab legkisebb fokszámértékhez tartozó csúcsok közül bármelyik kettő fokszámösszege kisebb, mint $n$. Viszont feltettük, hogy az Ore-féle feltétel teljesül, ezért ez azt jelenti, hogy ez a $k$ csúcs páronként össze van kötve egymással, azaz egy $k$ csúcsú teljes részgráfot alkotnak. Emiatt viszont – mivel fokszámaik nem nagyobbak $k$-nál, de már van $k-1$ db szomszédjuk – mindegyik legfeljebb egy további csúccsal lehet összekötve a maradék $n-k$ csúcs közül. Azonban $n-k>k$ (hiszen $k<\frac{n}{2}$) a maradék $n-k$ csúcs között maradni fog olyan, amelyiknek nincs az előbbi $k$ csúcs közötti szomszédja. Ennek a csúcsnak mindegyik szomszédja a maradék $n-k$ csúcs közül fog kikerülni, így a fokszáma maximum $n-k-1$. Ezek szerint ezen csúcs és az első $k$ csúcs bármelyike egyrészt összekötetlen, másrészt fokszámaik összege legfeljebb $k+n-k-1=n-1$, ami viszont ellentmond az Ore-féle feltételnek, pedig arról feltettük, hogy teljesül. Ez az ellentmondás bizonyítja az állítást.

Hivatkozások

• Katona–Recski–Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003.