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\geq 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)\geq 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^{'}\$. Húzzunk be $G^{'}\$-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)\leq n-1-d(x)$$d(y)+d(x)\leq n-1$

ami viszont ellentmondás, hiszen $d(y)+d(x)\geq 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: $\exists k<{\frac {n}{2}}$, amire $d_{k}\leq k$. Rögzítsünk le egy ilyen $k\$-t! Mivel $d_{1}\leq ...\leq d_{k}\leq 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.