Demonstratie: Procedura FazaTaieturiiMinime sorteaza nodurile grafului curent, incepand cu a si terminand cu $s$ si cu $t$, in functie de ordinea in care acestea au fost adaugate in multimea $A$. Vom analiza o taietura $C$ $s-t$ oarecare a grafului curent si vom demonstra ca are costul mai mare sau egal cu cel al taieturii faza.

Numim un nod $v ≠ a$ activ (in raport cu taietura $C$) daca $v$ si ultimul nod aduagat inainte de $v$ se afla in multimi diferite. Fie $w(C)$ costul taieturii $C, A{~v~}$ multimea nodurilor adaugate inaintea lui $v, C{~v~}$ taietura lui $A{~v~} ∪ v$ indusa de $C$, iar $w(C{~v~})$ costul taieturii induse.

Numim un nod $v ≠ a$ activ (in raport cu taietura $C$) daca $v$ si ultimul nod adaugat inainte de $v$ se afla in multimi diferite. Fie $w(C)$ costul taieturii $C, A{~v~}$ multimea nodurilor adaugate inaintea lui $v, C{~v~}$ taietura lui $A{~v~} ∪ v$ indusa de $C$, iar $w(C{~v~})$ costul taieturii induse.

Vom arata prin inductie ca pentru fiecare nod activ $v$,