Spanning Trees and Graphs Suppose $Z_1$ and $Z_2$ are two different spanning trees of a simple connected undirected graph $H$. Show that if $a_1$ is an edge in $Z_1$ that is not in $Z_2$, then there is an edge $a_2$ in $Z_2$ that is not in $Z_1$ such that the graph ($Z_1$ − $a_1$) + $a_2$ (obtained from $Z_1$ on replacing $a_1$ by $a_2$) is also a spanning tree of $H$.
This is a practice problem assigned in the book, but the answer provided is a little confusing. Could someone break this down a little better?
Answer provided: Essentially, it breaks it down through the associative property of addition between the two spanning trees. Since the two spanning trees are of a simple connected graph, subtracting one edge from a tree and adding an edge that is not in the previous tree will produce a spanning tree that is still representative of the graph H.
 A: Observe that since $a_1\in E(Z_1)\setminus E(Z_2)$ then $Z_2+a_1$ contains a cycle $C$. Suppose $a_1=uv$. Thus the only $uv$-path in $Z_1$ is $a_1$ and the only $uv$-path $P$ in $Z_2$ is $C-a_1$. Now we can see that there exists an edge $a_2$ in $P$ that is not in $Z_1$ (or else $C$ would be a cycle in $Z_1$ which is not possible).
Observe that in $Z_1+a_2$ there is a unique cycle $C'$ that contains edges $a_1$ and $a_2$. Let $Q$ denote the $uv$-path resulting from $C'$ by removing the edge $a_1$.
Let $Z_3=Z_1-a_1+a_2$. Below we show $Z_3$ is a spanning tree of $H$.


*

*$Z_3$ is spanning. Clearly since no vertices are being deleted.

*$Z_3$ is a tree. First we show $Z_3$ is connected. Let $x,y\in V(Z_3)$. We prove there is an $xy$-walk in $Z_3$. Since $Z_1$ is connected, there exists and $xy$-walk $W$ in $Z_1$. Replace any occurrence of $a_1$ in $W$ by $Q$ to obtain $W'$. Clearly $W'$ is an $xy$-walk in $Z_3$. 
Now, $Z_3$ is connected (by 2), has $|V(H)|$ vertices (by 1) and $|V(H)|-1$ edges (since $|E(Z_3)|=|E(Z_1)|-1+1=|E(Z_1)|=|V(H)|-1$), thus it is a spanning tree.
