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

• Ha teljesül a következő feltétel: (+) ${\displaystyle \forall k}$-ra, amelyre ${\displaystyle d_{k}\leq k<{\frac {n}{2))}$ teljesül, hogy ${\displaystyle d_{n-k}\geq n-k}$ akkor ${\displaystyle G\ }$ tartalmaz Hamilton-kört.
• Ha ${\displaystyle 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ó ${\displaystyle G\ }$ gráf, melynek ${\displaystyle d_{1}^{'}\leq d_{2}^{'}\leq \ldots \leq d_{n}^{'))$ fokszámaira ${\displaystyle \forall i}$-re ${\displaystyle 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 ${\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 (${\displaystyle n\geq 3}$ esetén) 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. Azaz ${\displaystyle 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. (${\displaystyle n=2\ }$ esetén is van Hamilton-út, ${\displaystyle 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: ${\displaystyle v_{1},v_{2},\ldots ,v_{n}\ }$, és ${\displaystyle v_{1}=x\ }$ és ${\displaystyle v_{n}=y\ }$. Ha ${\displaystyle x\ }$ szomszédos a P út valamely ${\displaystyle v_{i}\ }$ pontjával, akkor ${\displaystyle y\ }$ nem lehet összekötve ${\displaystyle v_{i-1}\ }$-gyel, mert ez esetben (${\displaystyle 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 ${\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}$ Azaz ${\displaystyle G\ }$-ben bármely két összekötetlen ${\displaystyle x,y\in V(G)}$-re ${\displaystyle 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 ${\displaystyle x,y\in V(G)}$-t úgy, hogy${\displaystyle \{x,y\}\notin E(G)}$ és ${\displaystyle 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 ${\displaystyle d(x)\leq d(y)}$. Így az előbbiekből következik, hogy ${\displaystyle d(x)\leq {\frac {n-1}{2))<{\frac {n}{2))}$. Bevezetünk egy új jelölést: ${\displaystyle d(x):=h\ }$. Megmutatjuk, hogy ${\displaystyle h\ }$-ra ${\displaystyle d_{h}\leq h<{\frac {n}{2))}$. Az előbb már láttuk, hogy ${\displaystyle 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 ${\displaystyle G\ }$-nek van legalább ${\displaystyle h\ }$ olyan csúcsa, amelyeknek a fokszámai külön-külön legfeljebb ${\displaystyle h\ }$. Tehát a ${\displaystyle h\ }$-adik legkisebb fokú csúcs fokszáma nem lehet ${\displaystyle h\ }$-nál nagyobb. Ezt akarjuk most belátni, hogy ez teljesül ${\displaystyle G\ }$-ben. Ehhez tekintsük ${\displaystyle x\ }$ minden szomszédjához az ${\displaystyle x\ }$ és ${\displaystyle y\ }$ közötti Hamilton-út mentén őt megelőzőt. Láttuk, hogy ezek egyike sem lehet összekötve ${\displaystyle y\ }$-nal, mert különben lenne ${\displaystyle G\ }$-ben Hamilton-kör. Ezek szerint viszont ezen összesen ${\displaystyle h\ }$ darab ilyen csúcs bármelyikét választhattuk volna ${\displaystyle y\ }$ párjául a tekintett Hamilton-út kezdőpontjának, és ha bármelyiknek a fokszáma nagyobb volna az ${\displaystyle x\ }$ fokszámánál, akkor a ${\displaystyle d(x)+d(y)\ }$ maximalizálásánál őt választottuk volna. De ${\displaystyle x\ }$-et választottuk, ezért biztos, hogy ezen ${\displaystyle h\ }$ darab csúcs egyikének sem nagyobb a fokszáma ${\displaystyle x\ }$ fokszámánál, vagyis ${\displaystyle h\ }$-nál. Azaz megkaptuk, hogy tényleg létezik ${\displaystyle G\ }$-ben legalább ${\displaystyle h\ }$ csúcs, melyeknek fokszáma nem nagyobb ${\displaystyle h\ }$-nál.

A feltételben szereplő ${\displaystyle k\ }$ helyébe ${\displaystyle h\ }$-t írva a fentiekből azt kapjuk, hogy ${\displaystyle d_{n-h}\geq n-h}$. Ez viszont pontosan azt jelenti, hogy legalább ${\displaystyle h+1\ }$ csúcs fokszáma legalább ${\displaystyle n-h\ }$. Mivel azonban ${\displaystyle x\ }$-nek ${\displaystyle h\ }$ darab szomszédja van, így az előbb említett ${\displaystyle h+1\ }$ csúcs között biztos van olyan, ami ${\displaystyle x\ }$-szel nincs összekötve. Így találtunk két összekötetlen csúcsot, és ezek fokszámösszege legalább ${\displaystyle 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 (${\displaystyle u,v\in V(G)}$, ${\displaystyle \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 ${\displaystyle d_{1}\leq d_{2}\leq \ldots \leq d_{n))$ pozitív egészekre (pozitív kell, hiszen ha valamely csúcs foka ${\displaystyle 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 ${\displaystyle \exists k<{\frac {n}{2))}$, amire egyrészt ${\displaystyle d_{k}\leq k}$, másrészt pedig ${\displaystyle d_{n-k}<n-k\ }$. Ebből viszont a következő három összefüggés következik:

${\displaystyle d_{1}\leq d_{2}\leq \ldots \leq d_{k}\leq k}$

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

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

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

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

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

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

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