Tutte-tétel
A Tutte-tétel arról szól, hogy mikor van egy gráfban teljes párosítás. Először Tutte bizonyította be 1947-ben, majd Gallai Tibor adott rá elemi bizonyítást.
Teljes párosításra tétel még a Frobenius-tétel.
Tétel
[szerkesztés]Egy gráfban akkor és csakis akkor létezik teljes párosítás, ha akárhogy hagyunk el a gráfból néhány pontot, a maradékban a páratlan komponensek száma ennél nem több.
A tétel bizonyítása
[szerkesztés]Legyen G=(V,E) (irányítatlan) gráf. Ha van a gráfban teljes párosítás, akkor egyszerű a helyzet. Elég ugyanis az élek elhagyása után megszámolni a páratlan pontszámú komponenseket. Az egyenlőtlenségnek teljesülnie kell, mert a leszűkített párosításban minden komponensben kimarad egy pont, tehát ezek az elhagyott pontokkal vannak párban a teljes párosítás szerint.
A másik irány nehezebb. Ehhez szükséges néhány jelölés és definíció.
Legyen H részgráfja G-nek. Ekkor cp(H) jelölje a H-beli páratlan elemszámú komponensek számát.
Definíció: X gát, ha cp(G-X)=|X|. Van gát, mert az üres halmaz gát.
Most feltesszük, hogy |V|=n páros. Ekkor, ha X nem gát, akkor cp(G-X)=|X|-2 n páros volta miatt. Legyen a legnagyobb gát X0.
Lemma: G\X0-ban nincsenek páros pontszámú komponensek.
Ha ugyanis lenne, akkor az egyikből kivéve egy pontot, és X0-hoz hozzávéve nagyobb gátat lehetne létrehozni, mivel cp(G\X0\p)=|X0|+1.
Lemma: Ha K páratlan elemszámú komponens G\X0-ban, és a p pont K-beli, akkor K\p-nek van teljes párosítása.
Ha ugyanis nem teljesülne, akkor lenne egy X halmaz K\p-ben, hogy cp(K\p\X)>|X|. Ekkor X0-t kibővítve p-vel és X-szel nagyobb gátat lehetne létrehozni, ami 2-vel nagyobb.
Most már rá lehet térni a tétel másik irányának bizonyítására.
Tekintsük G\X0-t. Ebben nincsenek páros méretű komponensek, és annyi páratlan méretű komponens van, ahány elem X0-ban. Készítünk egy segédgráfot, ahol nem vesszük figyelembe a gát pontjai között futó éleket. Ebben akkor és csak akkor van teljes párosítás, ha teljesül a Hall-feltétel. Márpedig ez teljesül, különben a tétel feltétele megsérül.
Források
[szerkesztés]- Katona-Recski-Szabó Csaba: Véges matematika
- Lovász László: Combinatorial Problems and Exercises
- Hajnal Péter: Gráfelmélet
