Let $T_1$ and $T_2$ be two spanning trees of a graph $G$. Prove that if $e$ is an edge of $T_1$, there exists an edge $f$ in $T_2$ so $T_1-\{e\}+\{f\}$ also is a spanning tree.
For $\{e\}\subset T_2$, it is quite trivial, you just choose $f=e$. But for $\{e\} \not\subset $T_2$, I can't seem to figure out the proof.
On
Consider partitioning the vertex set $V$ into two parts, $A$ and $B$. Any spanning tree clearly must have a path from $A$ to $B$, as they are disjoint and the tree is spanning. However, since they cover $V$ completely, this path must be an edge.
Then, consider removing $e$. This splits it into two such partitions. Since $T_{2}$ is a spanning tree, by above, it must have an edge which reconnects the graph.
Removing $e$ separates $T_1$ into two components, which can be interpreted as a partition of the vertices into two sets $V_1$ and $V_2$. $T_2$ is a spanning tree of the graph, so there must be an edge connecting a vertex of $V_1$ to a vertex of $V_2$.