MST theorem intuition We learned this theorem.
Given an undirected graph $G$ with weight function $w : E \rightarrow \mathbb{R}$, if $T$ and $T'$ are two MST's (minimum spanning trees) of $G$, with distinct edges ($ \cap ′= \varnothing$), then $T$ has two edges with the same weight.
Can you help and give an intuition for this theorem and why it is true and how to prove it?
thanks
 A: Let $e'$ be an edge with minimum weight in $T \cup T'$. Suppose for the moment that $e'$ is in $T'$. Then by assumption, $e'$ is not in $T$. It is well-known that in this case $T + e'$ contains a circuit $C$ and that for any edge $e \in C$, $T + e' - e$ is a spanning tree. The cost of this tree is $w(T) + w(e') - w(e) \leq w(T)$ (here we use the minimality of $e'$). But since $T$ was a MST , we can't have strict inequality here, and it follows that $w(e) = w(e')$. This holds for every edge of $C$, and since $C$ was a circuit in $T+e'$, it must have at least three edges, and so at least two edges in $T$.
What if $e'$ was in $T$ and not $T'$? Well, the previous argument showed that there is, after all, an edge (in fact, at least two edges) in $T'$ with the same weight as $e'$, so we can still assume that $e'$ is in $T'$.
Edit: I don't have a really good intuition for why this works, but the following ideas may be helpful in thinking about this and similar problems. It is well-known that the greedy algorithm (also known as Kruskal's algorithm) finds a MST. What is less commonly known is that every MST arises as the output to the greedy algorithm. That is, for any MST $T$, we can make the greedy algorithm output $T$ by choosing appropriately whenever we have a choice between multiple edges (necessarily of the same weight).
This somehow suggests that the more edges in $G$ there are with the same weight, the more MSTs we can find, and vice versa. Indeed, it immediately gives that if every edge weight is distinct, then there is a unique MST. It also shows that in every MST there is an edge that is a cheapest edge in $G$. So if there is a unique cheapest edge, then we can't have two edge-disjoint MSTs. On the other hand, if there are at least two cheapest edges in $G$, then every MST will contain at least two such edges, since the first two choices of the greedy algorithm will be from among these. So we get another proof of your theorem, modulo the fact that the greedy algorithm finds every MST. But the proof of the latter uses very similar ideas to those in my original proof.
