Definíció: Két él függetlensége: nincs közös végpontja két nem hurokélnek. Élhalmaz függetlenesége: páronként független nem gurokélek. v(G) a maximális méretû párosítás nagysága.
Definíció: Lefogó ponthalmaz: olyan ponthalmaz, hogy minden élnek legyen ebbe tartozó végpontja. T(g) a minimális méretû lefogó ponthalmaz nagysága.
Megjegyzés: Minden G gráfra v(G)<=T(G).
Megjegyzés: Egy páratlan pontszámú kör mutatja, hogy az egyenlõség nem szükségszerû.
Tétel (Kõnig tétele): Páros gráfokban v(G)=T(G).
Bizonyítás: A G páros gráfor kiegészítjük egy felsõ s csúcsal, amelyet a felsõ színosztály összes elemével összekötünk, illetve egy t alsó csúccsal, amelyet az alsó színosztály összes elemével összekötünk, majd minden élet lefelé irányítunk. Menger tételébõl adódik az állítás.
Következmények:
Definíció: Kõnig-akadály. Alsó pontok egy olyan K halmaza, amely szomszédsága kisebb mint K elemszáma.
Kõnig-akadály léte mellett egy páros gráfban nem lehet alsó pontokat lefedõ párosítás.
Tétel: Egy páros gráfban akkor és csak akkor van az összes alsó ponto lefedõ párosítás, ha nincs benne Kõnig-akadály.
Bizonyítás: Egy lefogó ponthalmaznak valamely X alsó ponthalmazt és ennek szomszédságán kívüli felsõ pontokat kell tartalmaznia. Kõnig-akadály hiánya esetén ez legalább |A| darab pont. Azaz a minimális lefogó ponthalmaz mérete pontosan |A|
Tétel: Egy páros gráfban akkor és csak akkor van teljes párosítás, ha nincs benne Kõnig-akadály és az alsó, illetve felsõ csúcsok száma megegyezik.
Bizonyítás: Az elõzõ tételbõl egyszerûen következik.
Megjegyzés: Egy K Kõnig-akadály létezésébõl az is könnyen látható, hogy a páros graunk minden párosítása legalább |K|-|N(K)| csúcsot párosítatlanul hagy. Also csúcsok azon K részhalmazát véve, amire |K|-|N(K)| a maximális, az így kapott érték alsó becslés lesz |A|-v(G)-re. A következõ tétel alapján ez nem csak becslés, hanem egyenlõséget is állíthatunk.
Tétel: |A|-v(G)=max{|K|-|N(K)|: K alsó pontok halmaza}
Bizonyítás: Az egyik irány következik a fenti megjegyzésbõl. A másik irányt nem bizonyítjuk.
Definíció: Tutte-akadály a gráf egy olyan
Tétel (Tutte-tétele): Egy gráfben 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ását a következõ órán fejezzük be.