Minimal Spanning Tree for Graph $G=(V,E)$ Let $G=(V,E)$ be a connected graph, undirected and weighted.
Define $f_w: E \to R^+$ as the weight function on $G$ edges.
Let $T_1 = (V, E_1)$ be a $MST$ for $G$ and Let $T_2 = (V, E_2)$ spanning tree for $G$ such that $f_w(T_2) > f_w(T_1)$
Prove there exists $e_2 \in E_2\setminus E_1$ such that if we add $e_2$ to $T_1$, it will form a circle $C$  which contains an edge $e_1\in E_1 \setminus E_2$ such that $f_w(e_2) > f_w(e_1)$.
I'm trying to prove this claim through assuming by contradiction as follows:
If there exists an edge $e_1\in E_1 \setminus E_2 \cap C$ such that $f_w(e_1) > f_w(e_2)$ than $T_3 = (V, E_1\cup{\{e_2}\}\setminus{\{e_1}\})$ is a spanning tree for $G$ that applies $f_w(T_3) < f_w(T_1)$, which is contradiction for $T_1$ being the minimal spanning tree.
Now I'm stuck at the point where each $e_1\in E_1 \setminus E_2 \cap C$ applies $f_w(e_1) = f_w(e_2)$, and I'm not sure how to contradict this one.
Thanks!
 A: Let $e_3 \in E_2 \backslash E_1$, and let $g_3 \in E_1 \backslash E_2$ where $g_3$ is an edge in the cycle $C_3$ of $T_1 \cup e_3$. Then, as you've pointed out, either $f_w(g_3) > f_w(e_3)$ and we are done, or $f_w(g_3) = f_w(e_3)$.
In the latter case, let $T_3 = (V, E_3) = (V, E_2 \cup \{g_3\}) \backslash \{e_3\}$. That is, $T_3$ is just $T_2$ with an edge exchanged for an edge of $T_1$. We can perform the same process on $T_3$. Let $e_4 \in E_3 \backslash E_1$, and let $g_4 \in E_1 \backslash E_3$ where $g_4$ is an edge in the cycle $C_4$ of $T_1 \cup e_4$. Again, either $f_w(g_4) > f_w(e_4)$, or $f_w(g_4) = f_w(e_4)$.
In this way, we can make a sequence $(T_2, T_3, T_4, \ldots, T_{n+2})$ where $E_i = E_{i-1} \cup \{e_i\} \backslash \{g_i\}$ for $i \geq 4$. Then $T_{n+2} = T_1$. At some point in the sequence $(f_w(T_2), f_w(T_3), f_w(T_4), \ldots, f_w(T_{n+2}))$, the value must decrease. If, for instance, $f_w(T_{i-1}) > f_w(T_i)$, then the edge $e_i$ that you used to construct $T_i$ is the edge you want according to the problem statement.
