CLRS 23.1-8 List of sorted edges remains the same

[CLRS 23.1-8]: Let $T$ be a minimum spanning tree of a graph $G$, and let $L$ be the sorted list of the edge weights of $T$. Show that for any other minimum spanning tree $T'$ of $G$, the list $L$ is also the sorted list of edge weights of $T'$ .

Note that $w(T) = w(T')$.

Well, assume that the sorted list of edges for $T'$ is $L'$, which is different from $L$. Then there will be atleast one edge that is excluded (say edge $a$), and an another edge (say $b$) is added to $L'$. Each edge connects one vertex. So we'll have a vertex, (say $\alpha$) which was connected via $a$ in $T$, but in $T'$, it's connected via $b$. If $w(a) = w(b)$, then $L' =L$, so there's no problem. But if the $w(a) \neq w(b)$, then we would have $w(T) \neq w(T')$, which is contradictory. This could only be solved by:

Assume that $w(a) > w(b)$, then we'll have another edge $c$ in $T$, that is replaced by $d$ in $T'$. Moreover, $w(c) < w(d)$, so that $w(a)+w(c) = w(b)+w(d)$, because of which $w(T) = w(T')$. But if that was always possible, then we'll simply take $b$ instead of $a$, and $c$ instead of $d$, thus reducing the total weight, contradicting the fact that $T$, and $T'$ are MSTs.


Therefore, $L$ must be equal to $L'$. Cool. Super cool.