Ore-tétel

1. Sablon:Label Az 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.

---

Ore-tétel

Az **Ore-tétel** a gráfelmélet egyik fontos tétele, amely egy gráf Hamilton-körének létezésére ad elegendő feltételt. A tétel kimondja, hogy ha egy gráf csúcsai között bizonyos fokszámok összege elég nagy, akkor a gráf tartalmaz Hamilton-kört.

Tétel

Legyen $G=(V,E)$ egy $n$-csúcsú egyszerű gráf ($n\ge 3$). Ha bármely két nem szomszédos csúcs fokszámának összege legalább $n$, azaz:

$$\mathrm{deg}(u)+\mathrm{deg}(v)\ge n\text{minden }u,v\in V\text{ nem szomszédos csúcsra},$$

akkor $G$ tartalmaz Hamilton-kört.

---

Bizonyítás

1. Indirekt bizonyítás

Tegyük fel, hogy $G$ nem tartalmaz Hamilton-kört. Ez ellentmondásra vezet a feltétellel.

---

2. Egy Hamilton-út létezése

Legyen $P$ a $G$ gráfban egy maximális Hamilton-út, amely $v_1,v_2,\dots ,v_k$ csúcsokból áll, ahol $k\le n$. Ez azt jelenti, hogy $P$-hez nem adható hozzá további csúcs úgy, hogy az út továbbra is Hamilton-út maradjon.

---

3. Maximális út tulajdonságai

A maximális Hamilton-út $P$ tulajdonságaiból következik, hogy:

• A $P$ végpontjai ($v_1$ és $v_k$) nem kapcsolhatók össze, különben $P$-ből Hamilton-kört lehetne alkotni, ami ellentmond a feltételezésnek.
• A $v_1$-gyel nem szomszédos csúcsoknak a $P$-n belül létezniük kell, és ugyanez igaz a $v_k$-ra is.

---

4. Fokszámok összege és kapcsolódási lehetőség

Tekintsük $v_1$ és $v_k$ fokszámát. Az Ore-feltétel szerint:

$$\mathrm{deg}(v_1)+\mathrm{deg}(v_k)\ge n.$$

Ez azt jelenti, hogy $v_1$ és $v_k$ fokszámainak összege elég nagy ahhoz, hogy legalább $n$-nyi csúcsot lefedjenek.

---

5. Út bővíthetősége

Ha $v_1$-hez vagy $v_k$-hoz szomszédos csúcsok révén bővítenénk az $P$-t, akkor ellentmondásra jutnánk, mert $P$ már maximális Hamilton-út, és nem tartalmazhat további csúcsot.

Ezért az Ore-feltétel megsértése nélkül $P$-t ki lehetne egészíteni, így Hamilton-kört alkotva. Ez ellentmond az eredeti feltételezésünknek.

---

6. Következtetés

Mivel az Ore-feltétel teljesül, és $P$-ből mindig létrehozható Hamilton-kör, a gráf $G$ tartalmaz Hamilton-kört.

---

Megjegyzés

Az Ore-tétel általánosabb, mint a Dirac-tétel, amely szerint ha egy gráfban minden csúcs fokszáma legalább $n/2$, akkor a gráf tartalmaz Hamilton-kört. Az Ore-tétel gyengébb feltételekkel is garantálja Hamilton-kör létezését.

---

Példa

Legyen $G$ egy 6 csúcsú gráf ($n=6$), ahol minden nem szomszédos csúcs fokszámának összege legalább 6. Az Ore-tétel alapján $G$-nek léteznie kell Hamilton-körnek.

Egy lehetséges gráf például:

• Csúcsok: $V=\{1,2,3,4,5,6\}$,
• Élek: $E=\{(1,2),(2,3),(3,4),(4,5),(5,6),(6,1)\}$.

---

Összefoglalás

Az **Ore-tétel** egy elegendő feltételt ad Hamilton-kör létezésére egy gráfban, amely a csúcsok fokszámának összegére épül. A tétel fontos szerepet játszik a gráfelméletben, különösen a Hamilton-körök létezésének vizsgálatában.

• Sablon:En: Sablon:T