Can someone please verify my proof or offer suggestions for improvement?
Let $T, T'$ be two spanning trees of a connected graph $G$. For $e \in E(T)-E(T')$, prove that there is an edge $e' \in E(T')-E(T)$ such that $T'+e-e'$ and $T-e+e'$ are both spanning trees of $G$.
Let $e = \{x, y\}$. There exists a path $x, u_1, u_2, \ldots u_k, y$ in $T'$. There exists an edge $e' = \{u_d, u_{d+1}\}$ such that $e' \notin T$. If that weren't the case, then the union of $x, y$ and $x, u_1, u_2, \ldots u_k, y$ would form a closed path. Remove edge $e'=\{u_d, u_{d+1}\}$ and add edge $\{x,y\}$ to $T'$. Then, the graph $T'+e-e'$ is connected. To see this, let $\alpha$ and $\beta$ be two vertices in $G$. There exists a path $p$ in $T'$ from $\alpha$ to $\beta$. If $p$ includes $\{u_d, u_{d+1}\}$, form a path $p'$ in $T'+e-e'$ by deleting $u_d, u_{d+1}$, and inserting $u_{d+1}, u_{d+2}, \ldots, x, u_1, u_2, \ldots u_{d-1}, u_d$ in its place. Then, the new path connects $\alpha$ to $\beta$ in $T'+e-e'$. Since $T'+e-e'$ contains $n$ vertices and $n-1$ edges and is connected, it is a spanning tree.
Using similar reasoning, it can be shown that $T-e+e'$ is a spanning tree.
Best Answer
It's seems legitimate. Here's some feedback.
I suggest "There exists a path $x, u_1, u_2, \ldots u_k, y$ in $T'$." be prefaced with "Since $e \not\in E(T')$, ..." or maybe "Since $T'$ is a tree...".
I try to avoid structures like "[Claim] is true. This is because...." because the reader can be left thinking Why is [Claim] true? without realizing that it's proved in the next sentence.
I feel these can be improved by using "[Claim] is true, otherwise ..." or "[Claim] is true (otherwise ...)." or "If [Claim] is false, then [contradiction]. So [Claim] is true."
E.g. "Then, the graph $T'+e-e'$ is connected. To see this, ..."
E.g. "There exists an edge $e' = \{u_d, u_{d+1}\}$ such that $e' \notin T$. If that weren't the case, ...". This statement also has the disadvantage of not including the edges $\{x,u_1\}$ and $\{u_k,y\}$.
Consequently, it might be better to define $P$ as the path $x, u_1, u_2, \ldots u_k, y$, and say "If $P$ is completely contained in $T$, then $P \cup e$ is a cycle in $T$, contradicting the assumption that $T$ is a tree. Hence there is some edge $e' \in P$ that's not in $T$."
Where did $G$ come from? It should be $T'$?
$p'$ might not be a path (it might reuse edges and vertices), but would be a walk.
"$u_{d+1}, u_{d+2}, \ldots, x, u_1, u_2, \ldots u_{d-1}, u_d$" should be "$u_{d+1}, u_{d+2}, \ldots, u_k, y, x, u_1, u_2, \ldots u_{d-1}, u_d$". And isn't it backwards?
Rather than "Using similar reasoning...", we can apply the proof with $T$ and $T'$ swapped to complete the full proof.