Para ver que 2 es cierto, consideremos dos MST diferentes $T_1$ y $T_2$ demostraremos que, o bien $T_1=T_2$ (es decir, no son diferentes) o uno de ellos no es realmente mínimo. Como ambos son mínimos, la suma del peso de cada arista es la misma. Digamos que las aristas de $T_1$ son $e_1 < e_2 < ... < e_n$ y los bordes de $T_2$ son $f_1 < f_2 < ... < f_n$ . Como los árboles son diferentes (por hipótesis) hay (al menos) una arista que es diferente: digamos $e_i\in T_1$ y $e_i\notin T_2$ ... elegir $e_i$ como la arista más pequeña con esta propiedad, es decir $e_1=f_1, e_2=f_2, ..., e_{i-1}=f_{i-1}$ y $e_{i} < f_{i}$ .
A continuación, añada $e_{i}$ a $T_{2}$ . Has creado un ciclo, así que ahora borramos una arista para convertirlo en un árbol. Elimina la arista de máximo peso en el ciclo, $f_{j}$ . Siempre que la arista que hemos eliminado ( $f_j$ ) no es $e_{i}$ entonces el nuevo Árbol $T_{2}+e_{i}-f_{j}$ tiene menor peso que $T_{2}$ y por lo tanto $T_{2}$ no era un MST (contradicción). Ahora, sólo tenemos que demostrar que $e_{i}$ no es $f_{j}$ .
Si $e_{i}$ es $f_{j}$ eso significa que la arista que añadimos era la más pesada del ciclo (tenía el mayor peso). Si este es el caso, entonces todas las aristas del ciclo son más ligeras y, por lo tanto, aparecen antes en el ordenamiento (es decir, todas las aristas del ciclo tienen subíndices menores que $i$ ). Pero, entonces todas estas aristas están también en $T_1$ y $e_i$ está en $T_1$ pero $T_1$ es un árbol y no contiene ningún ciclo. Por lo tanto, hay una arista en el ciclo que no está en $T_{1}$ y, por tanto, tiene más peso que $e_{i}$ . Así, $e_{i}$ no es $f_{j}$ .
