La condition est suffisante

La preuve de suffisance de cette condition utilise la condition sur les coupes, ce qui permet de mettre en évidence la connection forte entre ces deux notions. Soit $T^*$ un arbre satisfaisant la condition et $(i,\,j)$ un arc quelconque de cet arbre. Supprimons le, on crée alors une coupe $[S, \, \overline{S}]$ avec $i\:\in\:S$ et $j \: \in \: \overline{S}$. Soit l'arc $(k,\,l)$ appartenant à $[S, \, \overline{S}]$ mais n'appartenant pas à $T^*$. Comme $T^*$ est un arbre :

1. Il existe une chemin unique dans $T^*$ permettant de joindre $k$ à $l$
2. $(i,\,j)$ était le seul arc joignant $S$ à $\overline{S}$ et appartenant à $T^*$.

On en déduit que $(i,\,j)$ appartient au chemin joignant $k$ à $l$ dans $T^*$. et comme $T^*$ vérifie la condition on en déduit que $c_{ij} \leqslant c_{kl}$. Comme nous n'avons posé aucune condition particulière sur le choix de l'arc $(k,\,l)$, ce raisonnement s'applique à chaque arc de $[S, \, \overline{S}]$. On en déduit donc que $T^*$ vérifie la condition de coupe : il est donc optimal !