Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an algorithm which replaces an edge $\textit{e}$ in $\textit{T}$ by an edge $\textit{e'}$ not in $\textit{T}$, if $\textit{e' < e}$ and replacing it still maintains $\textit{T}$ to be a spanning tree.
I want to prove that this algorithm results in a minimum cost spanning tree of $\textit{G}$.
I am trying to prove this by contradiction - consider that $ \textit{T}$ is the tree which we obtain when the algorithm ends. We assume that there exists $\textit{T'}$ such that $\textit{W(T') < W(T)}$.
Attempt: I tried considering an edge $\textit{e}$ to be the lowest cost edge which is in $\textit{T'}$ but not in $\textit{T}$ (there is at least one since both are different spanning trees). We add $\textit{e}$ to $\textit{T}$ - thus, creating a cycle (since $\textit{T}$ was a spanning tree). There are two possible cases:
$\textit{e}$ is smaller than all the edges of the cycle it induced. But, in this case, the algorithm would not have stopped at $\textit{T}$, it would have replaced one of the edges of the cycle by $\textit{e}$.
$\textit{e}$ is larger than all the edges of the cycle it induced. I suppose this should contradict the minimality of $\textit{T'}$.
Am I anywhere on the right track? I don't know if considering the cycle is the way to do this.
