Edge exchange property of two Minimum Spanning Trees

Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T'

Then I want to prove the following:

For every edge e in T that's not in T', there is an edge e' in T'
that's not in T such that if we replace e with e' in T (let's call
it T_new) then it's still a minimal spanning tree of G.

I think I am too close for finding the right algorithm but stuck a little:

-
I have proved that weight(e) must be exactly equal to weight(e').

-
Since T is a tree, deleting e will result in 2 separated components, then for T_new to be a tree it must use one of the edges connecting two vertices from those different components.

But, I wasn't able to know which edge e' exactly will work. Plus I wasn't able to prove that always there is such an edge (I just found some requirements for e' that is must satisfy).

Some notes: I know Kruskal algorithm, and familiar with an algorithm in which we can paint some edges in yellow and request it to generate minimal spanning trees with maximum yellow edges (In other words from all found minimal spanning trees return the one with maximum number of yellow edges)

Here is a proof. Let $V$ be the vertices of $G$. $V$ are also the vertices of $T$ and the vertices of $T'$.

If $e$ is deleted from $T$, we will get two trees. Let the vertices of these two trees be $(V_1, V_2)$, which is a cut of $V$.

Since $T'$ is a tree, if we add $e$ to it, we will obtain a cycle. Since that cycle crosses $(V_1, V_2)$ at $e$, it must cross $(V_1, V_2)$ at another edge, say, $e'\in T'$.

• Since $T \setminus \{e\}\cup \{e'\}$ is a spanning tree of $G$ and $T$ is an MST, $\text{weight}(e) \le \text{weight}(e')$.

• Since $T' \setminus \{e'\}\cup \{e\}$ is a spanning tree of $G$ and $T'$ is an MST, $\text{weight}(e') \le \text{weight}(e)$.

So, $\text{weight}(e) = \text{weight}(e')$.

$T \setminus \{e\}\cup \{e'\}$, which is a spanning tree of the same weight as $T$, must be an MST of $G$. $\quad\checkmark$

StackExchange Computer Science Q#140094, answer score: 7