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 ${\displaystyle G}$ egy ${\displaystyle n\geq 3}$ csúcsú olyan egyszerű gráf, amire teljesül, hogy ha ${\displaystyle x,y\in V(G)}$ nem alkotnak élt (összekötetlenek), és ekkor ${\displaystyle d(x)+d(y)\geq n}$, akkor ${\displaystyle 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 ${\displaystyle G^{'}\ }$. Húzzunk be ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \{x,y\}\notin E(G)}$, hiszen egy ${\displaystyle n\ }$ csúcsú teljes gráfban van Hamilton-kör. Ekkor viszont a ${\displaystyle G\cup \{x,y\}}$ gráfban van Hamilton-kör, tehát ${\displaystyle G\ }$-ben van Hamilton-út. Legyenek a ${\displaystyle P}$ Hamilton-út csúcsai: ${\displaystyle v_{1},v_{2},...,v_{n}\ }$, és ${\displaystyle v_{1}=x\ }$ és ${\displaystyle v_{n}=y\ }$. Ha ${\displaystyle x\ }$ szomszédos a ${\displaystyle P}$ út valamely ${\displaystyle v_{i+1}\ }$ pontjával, akkor ${\displaystyle y\ }$ nem lehet összekötve ${\displaystyle v_{i}\ }$-vel, mert ez esetben (${\displaystyle 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 ${\displaystyle y\ }$ nem lehet összekötve legalább ${\displaystyle d(x)\ }$ darab ponttal, ezért

${\displaystyle d(y)\leq n-1-d(x)}$${\displaystyle d(y)+d(x)\leq n-1}$

ami viszont ellentmondás, hiszen ${\displaystyle 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 ${\displaystyle n}$ csúcsú ${\displaystyle G}$ gráfban nincs olyan ${\displaystyle x,y\in V(G)}$ pontpár, amelyre ${\displaystyle d(x)+d(y)<n\ }$ és ${\displaystyle \{x,y\}\notin E(G)}$, akkor ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle G\ }$ ${\displaystyle n\ }$ csúcsú egyszerű gráf, hogy teljesül rá az Ore-feltétel, de a Pósa-féle nem: ${\displaystyle \exists k<{\frac {n}{2}}}$, amire ${\displaystyle d_{k}\leq k}$. Rögzítsünk le egy ilyen ${\displaystyle k\ }$-t! Mivel ${\displaystyle d_{1}\leq ...\leq d_{k}\leq k<{\frac {n}{2}}}$, így a ${\displaystyle k\ }$ darab legkisebb fokszámértékhez tartozó csúcsok közül bármelyik kettő fokszámösszege kisebb, mint ${\displaystyle n\ }$. Viszont feltettük, hogy az Ore-féle feltétel teljesül, ezért ez azt jelenti, hogy ez a ${\displaystyle k\ }$ csúcs páronként össze van kötve egymással, azaz egy ${\displaystyle k\ }$ csúcsú teljes részgráfot alkotnak. Emiatt viszont – mivel fokszámaik nem nagyobbak ${\displaystyle k\ }$-nál, de már van ${\displaystyle k-1\ }$ db szomszédjuk – mindegyik legfeljebb egy további csúccsal lehet összekötve a maradék ${\displaystyle n-k\ }$ csúcs közül. Azonban ${\displaystyle n-k>k\ }$ (hiszen ${\displaystyle k<{\frac {n}{2}}}$) a maradék ${\displaystyle n-k\ }$ csúcs között maradni fog olyan, amelyiknek nincs az előbbi ${\displaystyle k\ }$ csúcs közötti szomszédja. Ennek a csúcsnak mindegyik szomszédja a maradék ${\displaystyle n-k\ }$ csúcs közül fog kikerülni, így a fokszáma maximum ${\displaystyle n-k-1\ }$. Ezek szerint ezen csúcs és az első ${\displaystyle k\ }$ csúcs bármelyike egyrészt összekötetlen, másrészt fokszámaik összege legfeljebb ${\displaystyle 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.