Tegyük fel indirekt, hogy $G$-nek mégis létezik egy olyan $e = \{a, b\}$ éle, amire $a \in A_1 \cup A_2$ és $b \in B_1 \cup B_3$. Ez összesen négy esetet jelent, amiket sorban kizárunk:

Jelölje $M$ élszámát $|M| = k$. Annak bizonyításához, hogy $M$ maximális, a lefogó ponthalmaz fogalmát hívjuk segítségül: meg fogjuk mutatni, hogy létezik $G$-ben $k$ pontú lefogó ponthalmaz. Ebből a korábban már látott gondolatmenet szerint valóban következni fog, hogy $M$ maximális: a $k$ méretű $M$ párosítás létezéséből $\nu(G) \geq k$, a $k$ pontú lefogó ponthalmaz létezéséből $\tau(G) \leq k$, ezekből az állításokból együtt pedig $k \leq \nu(G) \leq \tau(G) \leq k$ adódik. Következik, hogy $\nu(G) = k$, ami valóban azt jelenti, hogy $M$ maximális párosítás.

Azt állítjuk, hogy a Lemma jelöléseit használva $X = A_3 \cup B_2$ lefogó ponthalmaz $G$-ben. Legyen ugyanis $e = \{a, b\}$ tetszőleges éle $G$-nek, amire $a \in A$ és $b \in B$. Ha $a \in A_3$, akkor $e$-nek az $A$-béli végpontja $X$-béli, így $e$-t $X$ lefogja. Ha viszont $a \in A_1 \cup A_2$, akkor a Lemmából következik, hogy $b \in B_2$; így $X$ ebben az esetben is lefogja $e$-t.

Megmutatjuk még, hogy $|X| = k$. Ez abból adódik, hogy $X$ minden $M$-béli élnek pontosan az egyik végpontját tartalmazza: az $A_2$ és $B_2$ között futóknak a $B$-béli végpontját, az $A_3$ és $B_3$ között futóknak pedig az $A$-béli végpontját. Mivel $|M| = k$ és $X$ minden $M$-béli élnek egy végpontját tartalmazza, ezért $|X| = k$ is igaz.

A feltétel szükségessége nyilvánvaló: ha létezik $A$-t lefedő párosítás, akkor $|N(X)| \geq |X|$ minden $X \subseteq A$ esetén. Valóban, ha $M$ egy $A$-t lefedő párosítás, akkor az $X$ elemeinek $M$ szerinti szomszédjai mind $N(X)$-ben vannak és páronként különbözők, így $N(X)$-nek legalább $|X|$ eleme van. (Vagy ugyanez más megfogalmazásban: ha egy $X \subseteq A$ részhalmazra $|N(X)| < |X|$ teljesülne, akkor – ahogyan azt a tétel kimondása előtti példában is láttuk – nem juthatna már az $X$ minden elemének sem csupa különböző pár, így nem létezhetne $A$-t lefedő párosítás.)

Most belátjuk a feltétel elégségességét: ha $|N(X)| \geq |X|$ minden $X \subseteq A$ részhalmazra teljesül, akkor van $A$-t lefedő párosítás $G$-ben. Futtassuk ugyanis a javítóutas algoritmust a $G$ gráfra (tetszőleges párosításból indítva). Megmutatjuk, hogy az algoritmus leállásakor kapott $M$ párosítás lefedi $A$-t. Tegyük fel ugyanis indirekt, hogy nem ez a helyzet.

Lemma jelöléseit használva $N(A_1 \cup A_2) = B_2$ következik; valóban, a lemma állítása szerint $A_1 \cup A_2$ és $B_1 \cup B_3$ között nincs éle $G$-nek, ezért az $(A_1 \cup A_2)$-béliek minden szomszédja $B_2$-béli. Továbbá mivel $|A_2| = |B_2|$ (hiszen $A_2$ és $B_2$ elemeit az $M$ megfelelő élei párba állítják) és $A_1 \neq \emptyset$ (mert az $M$ nem fedi le $A$-t), ezért $|A_1 \cup A_2| > |B_2|$. Következik, hogy az $X = A_1 \cup A_2$ esetében sérül az $|N(X)| \geq |X|$ feltétel; ez az ellentmondás pedig bizonyítja a tétel állítását.

A feltétel szükségessége ismét nyilvánvaló: ha létezik $G$-ben teljes párosítás, akkor $|A| = |B|$ természetesen igaz és mivel egy teljes párosítás egyben $A$-t lefedő párosítás is, így azt már beláttuk, hogy $|N(X)| \geq |X|$ minden $X \subseteq A$ részhalmazra teljesül.

Megfordítva: ha $|N(X)| \geq |X|$ minden $X \subseteq A$ részhalmazra teljesül, akkor Hall Tétele miatt $G$-ben van $A$-t lefedő párosítás. De mivel $|A| = |B|$, ezért egy ilyen párosításnak nyilván $B$-t is fednie kell, így az teljes párosítás. Ezzel tehát a feltétel elégségességét is beláttuk.