Teorema 1: _Fie s si t doua noduri dintr-un graf G. Notam cu G/{s,t} graful obtinut din G prin fuzionarea nodurilor s si t. Atunci taietura minima a grafului G este cea mai mica dintre taietura minima s-t a grafului G si taietura minima a grafului G/{s,t}._

Teorema este adevarata deoarece facand o taietura minima in graf nodurile s si t fie vor fi in aceeasi multime (primul caz tratat), fie in multimi diferite (cel de-al doilea caz).

Teorema este adevarata deoarece facand o taietura minima in graf nodurile s si t fie vor fi in multimi diferite (primul caz tratat), fie in aceeasi multime (cel de-al doilea caz).

Asadar o procedura care gaseste o taietura minima _s-t arbitrara_ poate fi folosita pentru a construi un algoritm recursiv ce gaseste taietura minima.

h2. Corectitudine

Pentru a demonstra corectitudinea algoritmului, trebuie mai intai sa demonstram urmatoarea lema:
 
Lema 1: _Fiecare taietura faza reprezinta o taietura minima s-t, unde s si t sunt ultimele 2 noduri adaugate in faza curenta._
 
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.
 
Vom arata prin inductie ca pentru fiecare nod activ v,
 
    _w(A{~v~}, v) ≤ w(C{~v~})_
 
# Pentru primul nod activ, propizitia de mai sus este adevarata deoarece avem egalitate.
# Presupunem adevarata propozitia pentru toate nodurile active adaugate inaintea unui nod activ v, si fie u urmatorul nod activ ce urmeaza sa fie adaugat. Atunci avem:
 
    _w(A{~u~}, u) = w(A{~v~}, u) + w(A{~u~}\A{~v~}, u)_ = α
 
In continuare, avem w(A{~v~}, u) ≤ w(A{~v~}, v), deoarece atunci cand a fost ales, nodul v era mai puternic conectat decat u in raport cu A{~v~}. Prin inductie avem w(A{~v~}, v) ≤ w(C{~v~}). Toate muchiile dintre A{~u~}\A{~v~} si u conecteaza multimi diferite ale taieturii C. Deci ele contribuie la w(C{~u~}), dar nu si la w(C{~v~}). Asadar:
 
    _α ≤ w(C{~v~}) + w(A{~u~}\A{~v~}, u) ≤ w(C{~u~})_