La condition est nécessaire

Supposons qu'il existe une arête $(k,\,l) \, \in \, [S,\,\overline{S}]$ tel que $c_{kl} < c_{ij}$. Formons alors l'arbre $\overline{T} = T^* \backslash \{(i,\,j)\} \cup \{(k,\,l)\}$. $\overline{T}$ est un arbre car la suppression de $(i,\,j)$ crée une coupe à laquelle appartient également $(k,\,l)$. Du coup, l'ajout de $(k,\,l)$ n'ajoute pas de cycle et l'on obtient un arbre. Finalement, on obtient :

$$C(\overline{T}) = C(T^*) - c_{ij} + c_{kl}$$

or comme $c_{kl} < c_{ij}$, il en suit que $C(\overline{T}) < C(T^*)$ ce qui contredit l'hypothèse selon laquelle $T^*$ était optimal.