Ha $d = 0$, akkor a lemma állítása magától értetődő, így a továbbiakban feltesszük, hogy $d \ge 1$. Jelölje $G_f$ azt a gráfot, ami $G$ összes csúcsából és azokból az $e$ éleiből áll, amikre $f(e) = 1$. Azt kell megmutatnunk, hogy $G_f$-ben létezik $d$ éldiszjunkt irányított út $s$-ből $t$-be.

Ehhez először azt mutatjuk meg, hogy $G_f$-ben létezik irányított út $s$-ből $t$-be. $s$-ből indulva haladjunk „vaktában” $G_f$ élei mentén csak arra vigyázva, hogy egy élen csak egyszer menjünk át; állítjuk, hogy az így kapott $Q$ élsorozat $t$-ben akad el.

Ezért $Q$ valóban csak $t$-ben akadhat el. Persze $Q$ nem feltétlen út, hiszen egy csúcsot többször is érinthet, de $Q$-ból az ismétlődő csúcsok előfordulásai közötti részeket sorra kivágva irányított úthoz jutunk.

Válasszunk ezért $G_f$-ben egy $P_1$ irányított utat $s$-ből $t$-be; majd $P_1$ élein változtassuk meg a folyam értékét $f(e)=0$-ra. Ekkor $f$ továbbra is folyam (hiszen $P_1$ $s$-től és $t$-től különböző csúcsain $\sum f_{be}$ és $\sum f_{ki}$ is eggyel csökkent) és az értéke $m_f = d - 1$ lesz.

Ha most $d - 1 \ge 0$, akkor újra alkalmazhatjuk az előző bekezdés állítását: választhatunk egy olyan $P_2$ irányított utat $s$-ből $t$-be, aminek minden élére $f(e) = 1$. Ezt az eljárást addig folytathatjuk, amíg végül $m_f = 0$ lesz és megkapjuk a $P_1, P_2, \dots, P_d$ irányított utakat $s$-ből $t$-be.

Mivel ezek az utak nyilván éldiszjunktak (hiszen egy-egy út kiválasztása után annak az $e$ élein $f(e)$-t nullára állítottuk, így a későbbi utak ezeket már nem tartalmazhatták), ezért a lemmát beláttuk.

A tételt úgy látjuk be, hogy igazoljuk az $(i) \Rightarrow (ii)$, a $(ii) \Rightarrow (iii)$, valamint a $(iii) \Rightarrow (i)$ következtetések helyességét. Ezzel a bizonyítás valóban teljes lesz, hiszen bármelyik állításból eljuthatunk a másik kettőbe.

(i) $\Rightarrow$ (ii): Tegyük fel, hogy léteznek az $s$-ből $t$-be vezető $P_1, P_2, \dots, P_k$ éldiszjunkt irányított utak. Legyen $Z$ tetszőleges, az $s$-ből $t$-be vezető irányított utakat lefogó élhalmaz. Mivel $Z$ minden $s$-ből $t$-be vezető útból tartalmaz élt, ez igaz a $P_1, P_2, \dots, P_k$ utakra is; válasszunk ezért minden $1 \le i \le k$ esetén $P_i$-ből egy olyan $e_i$ élt, amire $e_i \in Z$. Ekkor az $e_1, e_2, \dots, e_k$ élek mind különbözők, hiszen a $P_i$ utak éldiszjunktak. Mivel tehát $Z$ tartalmaz $k$ különböző élt, ezért $|Z| \ge k$, amivel (ii)-t beláttuk.

(ii) $\Rightarrow$ (iii): Most azt tegyük fel, hogy (ii) teljesül, és legyen $X \subseteq V(G)$ tetszőleges vágás a $(G,s,t,c)$ hálózatban. Ekkor az $X$-ből kilépő élek nyilván lefogják az $s$-ből $t$-be vezető irányított utakat, hiszen $s \in X$ és $t \notin X$ miatt minden $s$-ből $t$-be vezető útnak tartalmaznia kell $X$-ből kilépő élt. (ii)-ből tehát következik, hogy $X$-ből legalább $k$ él lép ki. Ez fogalmazható úgy is, hogy $c(X) \ge k$, mert a definíció szerint $c(X)$ épp az $X$-ből kilépő élek száma (hiszen $c(e) = 1$ minden $e$ élre). Mivel tehát minden vágás kapacitása legalább $k$, ezért $\min\{c(X) : X \text{ st-vágás}\} \ge k$. Így a Ford-Fulkerson tételből $\max \{m_f : f \text{ folyam}\} \ge k$ következik, amivel (iii)-at beláttuk.

(iii) $\Rightarrow$ (i): Végül azt tegyük fel, hogy (iii) igaz és legyen $\max\{m_f : f \text{ folyam}\} = d$; ekkor tehát (iii) szerint $d \ge k$. Mivel $c$ egész értékű, ezért a Lemmából következően létezik olyan $f$ egész értékű folyam, amire $m_f = d$; rögzítsünk le egy ilyen $f$-et. Ekkor minden $e$ élre $f(e) = 0$ vagy $f(e) = 1$ (ismét azért, mert $c(e) = 1$ minden $e$ élre). Így $d \ge k$ miatt (i) valóban következik a folyamok felbontásáról szóló lemmából.

Legyen $k \ge 1$ tetszőleges egész. $\lambda_G(s,t) \ge k$ definíció szerint azt jelenti, hogy létezik $G$-ben $k$ éldiszjunkt (irányított vagy irányítatlan) út $s$-ből $t$-be.

$\lambda'_G(s,t) \ge k$ pedig azt jelenti, hogy az $s$-ből $t$-be vezető (irányított vagy irányítatlan) utakat lefogó élhalmazok minimális mérete legalább $k$; más szóval: nem létezik ilyen élhalmazból legföljebb $k - 1$ méretű.

A Tétel (i) és (ii) állításai közötti ekvivalencia azt jelenti (az irányított, illetve irányítatlan esetben), hogy $\lambda_G(s,t) \ge k$ pontosan akkor igaz, ha $\lambda'_G(s,t) \ge k$.

Ebből pedig $\lambda_G(s,t) = \lambda'_G(s,t)$ valóban következik, mert ugyanazoknál a $k$ egészeknél nagyobbak vagy egyenlők.