Chvátal-tétel

Sablon:Nincs forrás 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\le d_2\le \dots \le d_n$.

• Ha teljesül a következő feltétel: (+) $\mathrm{\forall }k$-ra, amelyre $d_k\le k<\frac{n}{2}$ teljesül, hogy $d_{n-k}\ge n-k$ akkor $G$ tartalmaz Hamilton-kört.
• Ha $d_1\le d_2\le \dots \le 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^{\text{'}}\le d_2^{\text{'}}\le \dots \le d_n^{\text{'}}$ fokszámaira $\mathrm{\forall }i$-re $d_i^{\text{'}}\ge 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^{\text{'}}$. Húzzunk be $G^{\text{'}}$-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\ge 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,\dots ,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,\dots ,v_{i-1},v_n,v_{n-1},\dots ,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)\le n-1-d(x)$$d(y)+d(x)\le n-1$ Azaz $G$-ben bármely két összekötetlen $x,y\in V(G)$-re $d(x)+d(y)\le 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)\le d(y)$. Így az előbbiekből következik, hogy $d(x)\le \frac{n-1}{2}<\frac{n}{2}$. Bevezetünk egy új jelölést: $d(x):=h$. Megmutatjuk, hogy $h$-ra $d_h\le 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}\ge 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)$, $\mathrm{\forall }\{u,v\}\notin E(G)\Rightarrow d(u)+d(v)\le n-1$). Ez az ellentmondás bizonyítja az állítást.

• Tegyük fel, hogy (+) nem teljesül valamely $d_1\le d_2\le \dots \le 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 $\mathrm{\exists }k<\frac{n}{2}$, amire egyrészt $d_k\le 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\le d_2\le \dots \le d_k\le k$ $d_{k+1}\le d_{k+2}\le \dots \le d_{n-k}\le n-k-1$ $d_{n-k+1}\le d_{n-k+2}\le \dots \le d_n\le n-1.$

Vagyis a $d_1^{\text{'}}\le d_2^{\text{'}}\le \dots \le d_k^{\text{'}}=k$

$d_{k+1}^{\text{'}}\le d_{k+2}^{\text{'}}\le \dots \le d_{n-k}^{\text{'}}=n-k-1$ $d_{n-k+1}^{\text{'}}\le d_{n-k+2}^{\text{'}}\le \dots \le d_n^{\text{'}}=n-1$

sorozatra teljesül, hogy $\mathrm{\forall }i$-re $d_i^{\text{'}}\ge d_i$. Ha tehát mutatunk egy olyan gráfot, amelynek fokszámai $d_1^{\text{'}}\le d_2^{\text{'}}\le \dots \le d_n^{\text{'}}$, é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. Sablon:Portál