Definíció: Tutte-akadály a gráf egy olyan ponthalmaz, amley elhjagyása után keletkezett pártalan pontszámú komponensek száma több mint az elhagyott pontok száma.
Tétel (Tutte-tétele): Egy gráfban akkor és csak akkor van teljes párosítás ha nincs benne Tutte-akadály.
Bizonyítás: A tétel egyik irány nyilvánvaló. A másik irány bizonyításához feltehető, hogy G páros pontú egyszerű gráf.
Indirekten bizonyítunk. Legyen G egy ellenpélda a tétel nem triviális irányára, azaz G nem tartalmaz Tutte-akadályt, de nincs benne teljes párosítás
Ekkor telítsük G-t úgy, hogy ne tartalmazzon teljes párosítást, de további él hozzáadásával keletkezzen teljes párosítás. Legyen G' a telített gráf.
Ha G-ben nem volt Tutte-akadály, akkor G'-ben sem lesz. így G' is egy ellenpélda. A telített G'-nek azonban szép struktúrája van.
Lemma: G'-ben legyen T azon pontok halmaza, amelyek minden más ponttal össze vannak kötve. Ekkor G'-T komponensei teljes gráfok.
A lemmából következik az állítás, mert a struktúrális ismereteink alapján könnyen látható, hogy ha T nem Tutte-akadály, akkor van teljes párosítás G'-ben.
A lemma egy átfogalmazása: V(G)-T-ben az ``összekötottnek vagy egyenlőnek lenni '' reláció ekvivalenciareláció.
A lemma (és így Tutte tételének) bizonyítása:
Tegyük fel, hogy nem igaz az állítás. Ekkor az állítás átfogalmazásaban szereplő reláció megsérti a tranzitívitást, azaz van három csúcs V(G)-T-ben, x,y,z, hogy xy és yz él, míg xz nem él. y nincs T-ben igy alkalmas t csúcsra yt nem él. G-t az xz, illetve yt élekkel bővítve G telítettsége miatt találhatunk M(1), illetve M(2) teljes párosításokat. Ezek uniója által alkotott élhalmaz V(G) pontjaival egy gráfot alkot, amelynek a két párosítás közös élei komponensei és ezeken kívüli komponensei páros hosszú körök, váltakozva M(1)-beli és M(2)-beli élekkel. Az xz, illetve yt a körök valamelyikére esik.
1. eset: xz, illetve yt különböző körre esik.
2. eset: xz, illetve yt azonos körre esik.
Mindkét esetben nem sok munkával G-beli M párosításhoz jutunk, ami ellentmondás.
Megjegyzés: Tutte-akadály létezése esetén kvalitatív becslés is adható arra, hogy legalább hány pontnak kell párosítatlanul maradnia.
Tétel (Berge-formula):
A fenti megjegyzás alapján bizonyítható
maximális ``deficit'' értéke |V(G)|-2v(G).
Bizonyítás:
Az egyik irány nyilvánvaló, a másik
irány végiggondolása egyszerű.