Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ by the following procedure?
- Let $G_0 := G_a$, $n=0$
- Choose an edge from $E$ that is not in $G_n$, and denote it $e$.
- Adding an edge in a tree will create exactly one unique cycle. Choose an edge in this new cycle formed by $G_n \cup\{e\}$, and remove it. Denote it as $G_{n+1}$.
- Set $n := n+1$
- Repeat steps 2-4.
Since every spanning tree will have the same number of edges (namely, $|V|-1$), the edges contained in $G_a$ but not in $G_b$ and the edges contained in $G_b$ but not in $G_a$ have the same cardinality and are distinct. However, it is not guaranteed that the new cycle formed in Step 3 will contain an edge that is contained in $G_a$ but not in $G_b$ so that it can be removed. If it can be proven, then from Step 2 we can simply choose an edge that is contained in $G_b$ but not in $G_a$, and remove an edge that is contained in $G_a$ but not in $G_b$, and proceed. Or is there any other indirect way to show it?
Every edge you see during the construction will be in either $G_a$ or $G_b$.
So if the new cycle you form on step 3 doesn't contain any edges outside $G_b$ it must be because the entire cycle consists of edges in $G_b$. But $G_b$, being a tree, does not contain any cycles -- contradiction!