Chvátal-tétel

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 $G\$ $n\$ csúcsú egyszerű gráf fokszámai nagyság szerint $d_{1}\leq d_{2}\leq \ldots \leq d_{n}$.

• Ha teljesül a következő feltétel: (+) $\forall k$-ra, amelyre $d_{k}\leq k<{\frac {n}{2}}$ teljesül, hogy $d_{n-k}\geq n-k$ akkor $G\$ tartalmaz Hamilton-kört.
• Ha $d_{1}\leq d_{2}\leq \ldots \leq d_{n}$ olyan pozitív egész számok, amikre (+) nem teljesül, akkor létezik olyan Hamilton-kört nem tartalmazó $G\$ gráf, melynek $d_{1}^{'}\leq d_{2}^{'}\leq \ldots \leq d_{n}^{'}$ fokszámaira $\forall i$-re $d_{i}^{'}\geq d_{i}$.

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 $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 ($n\geq 3$ esetén) van Hamilton-kör. Ekkor viszont a $G\cup \{x,y\}$ gráfban van Hamilton-kör, tehát $G\$-ben van Hamilton-út. Azaz $G\$ 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. ($n=2\$ esetén is van Hamilton-út, $n=1\$ esetén pedig a gráfunk egy izolált pont, nincs éle, nincs benne Hamilton-kör). Legyenek a P Hamilton-út csúcsai: $v_{1},v_{2},\ldots ,v_{n}\$, és $v_{1}=x\$ és $v_{n}=y\$. Ha $x\$ szomszédos a P út valamely $v_{i}\$ pontjával, akkor $y\$ nem lehet összekötve $v_{i-1}\$-gyel, mert ez esetben ($v_{1},v_{2},\ldots ,v_{i-1},v_{n},v_{n-1},\ldots ,v_{i},v_{1}\$) egy Hamilton-kör lenne. Í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$ Azaz $G\$-ben bármely két összekötetlen $x,y\in V(G)$-re $d(x)+d(y)\leq n-1$.

Most jön az, ami már különbözik az Ore-tétel bizonyításához képest. Válasszuk meg $x,y\in V(G)$-t úgy, hogy$\{x,y\}\notin E(G)$ és $d(x)+d(y)\$ 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 $d(x)\leq d(y)$. Így az előbbiekből következik, hogy $d(x)\leq {\frac {n-1}{2}}<{\frac {n}{2}}$. Bevezetünk egy új jelölést: $d(x):=h\$. Megmutatjuk, hogy $h\$-ra $d_{h}\leq h<{\frac {n}{2}}$. Az előbb már láttuk, hogy $h<{\frac {n}{2}}$, elég tehát az első egyenlőtlenséget belátnunk. Az első egyenlőtlenség jelentése pedig az, hogy $G\$-nek van legalább $h\$ olyan csúcsa, amelyeknek a fokszámai külön-külön legfeljebb $h\$. Tehát a $h\$-adik legkisebb fokú csúcs fokszáma nem lehet $h\$-nál nagyobb. Ezt akarjuk most belátni, hogy ez teljesül $G\$-ben. Ehhez tekintsük $x\$ minden szomszédjához az $x\$ és $y\$ közötti Hamilton-út mentén őt megelőzőt. Láttuk, hogy ezek egyike sem lehet összekötve $y\$-nal, mert különben lenne $G\$-ben Hamilton-kör. Ezek szerint viszont ezen összesen $h\$ darab ilyen csúcs bármelyikét választhattuk volna $y\$ párjául a tekintett Hamilton-út kezdőpontjának, és ha bármelyiknek a fokszáma nagyobb volna az $x\$ fokszámánál, akkor a $d(x)+d(y)\$ maximalizálásánál őt választottuk volna. De $x\$-et választottuk, ezért biztos, hogy ezen $h\$ darab csúcs egyikének sem nagyobb a fokszáma $x\$ fokszámánál, vagyis $h\$-nál. Azaz megkaptuk, hogy tényleg létezik $G\$-ben legalább $h\$ csúcs, melyeknek fokszáma nem nagyobb $h\$-nál.

A feltételben szereplő $k\$ helyébe $h\$-t írva a fentiekből azt kapjuk, hogy $d_{n-h}\geq n-h$. Ez viszont pontosan azt jelenti, hogy legalább $h+1\$ csúcs fokszáma legalább $n-h\$. Mivel azonban $x\$-nek $h\$ darab szomszédja van, így az előbb említett $h+1\$ csúcs között biztos van olyan, ami $x\$-szel nincs összekötve. Így találtunk két összekötetlen csúcsot, és ezek fokszámösszege legalább $h+n-h=n\$, 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 ($u,v\in V(G)$, $\forall \{u,v\}\notin E(G)\Rightarrow d(u)+d(v)\leq n-1$). Ez az ellentmondás bizonyítja az állítást.

• Tegyük fel, hogy (+) nem teljesül valamely $d_{1}\leq d_{2}\leq \ldots \leq d_{n}$ pozitív egészekre (pozitív kell, hiszen ha valamely csúcs foka $0\$, 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 $\exists k<{\frac {n}{2}}$, amire egyrészt $d_{k}\leq k$, másrészt pedig $d_{n-k}<n-k\$. Ebből viszont a következő három összefüggés következik:

$d_{1}\leq d_{2}\leq \ldots \leq d_{k}\leq k$ $d_{k+1}\leq d_{k+2}\leq \ldots \leq d_{n-k}\leq n-k-1$ $d_{n-k+1}\leq d_{n-k+2}\leq \ldots \leq d_{n}\leq n-1.$

Vagyis a $d_{1}^{'}\leq d_{2}^{'}\leq \ldots \leq d_{k}^{'}=k$

$d_{k+1}^{'}\leq d_{k+2}^{'}\leq \ldots \leq d_{n-k}^{'}=n-k-1$ $d_{n-k+1}^{'}\leq d_{n-k+2}^{'}\leq \ldots \leq d_{n}^{'}=n-1$

sorozatra teljesül, hogy $\forall i\$-re $d_{i}^{'}\geq d_{i}$. Ha tehát mutatunk egy olyan gráfot, amelynek fokszámai $d_{1}^{'}\leq d_{2}^{'}\leq \ldots \leq d_{n}^{'}$, és nincsen Hamilton-köre, akkor készen vagyunk.

A következő $G\$ gráf éppen ilyen. Az $n\$-elemű csúcshalmazt osszuk fel három részre: $A\$-ra, $B\$-re és $C\$-re, ahol $|A|=|B|=k\$ és $|C|=n-2k\$. A $B\cup C\$ halmazban levő csúcsokat kössük össze egymással (mindegyiket mindegyikkel). Így ezek a csúcsok meghatározzák $G\$ egy teljes $n-k\$ csúcsú feszített részgráfját. Ez után kössük össze mindegyik $A\$-beli csúcsot mindegyik $B\$-belivel, és csak ezek az élek legyenek a gráfban. Így megadtuk a $G\$ gráfot, könnyen ellenőrizhető, hogy fokszámai teljesítik az elmondottakat: minden $A\$-bel csúcs foka $k\$, a $B\$-belieké $n-2k+k-1+k=n-1\$, a $C\$-belieké pedig $n-2k-1+k=n-k-1\$. Már csak azt kell megmutatnunk, hogy $G\$-nek nincs Hamilton-köre. Ez pedig abból látható, hogy a $B\$-beli pontokat elhagyva a gráfból, a gráf $k+1\$ komponensre esik szét: az $A\$-beli pontokból $k\$ izolált pont lesz, a $k+1\$-edik komponens pedig a $C\$-n megmaradó teljes gráf. Fontos, hogy a $C\$ biztosan nem üres halmaz, hisz $|C|=n-2k\$, ami a $k<{\frac {n}{2}}$ feltétel miatt biztosan pozitív. $G\$-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.