Tétel (Kőnig tétele): Páros gráfokban v(G)=T(G).
Bizonyítás: Több bizonyítási módszer is adható. Ezeket itt nem részletezzük, de némelyikhez pointert adunk, némelyek kidolgozását a hallgatóra bízzuk.
III. bizonyítás: Legyen T(G)=k. G-ből hagyjunk el éleket addig, amíg fenn tudjuk tartani, hogy a tau-paraméter értéke k maradjon. Az így kapott gráfról belátható, hogy független éleket és izolált pontokat tartalmaz.
IV. bizonyítás: Teljes indukció.
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ány sem nehéz.