La condition est nécessaire

En remplaçant $(i,\,j)$ par $(j,\,k)$ dans $T^*$, on conserve la structure d'arbre couvrant. Si $c_{kl} < c_{ij}$, alors le remplacement de $(i,\,j)$ par $(k,\,l)$ permet d'obtenir un meilleur arbre ce qui contredit l'hypothèse d'optimalité.