# Given two spanning trees of a graph, shows edges can be traded between them to create 2 new spanning trees

The precise problem:

Let $T$, $T'$ be two spanning trees of a connected graph $G$. For $e \in E(T)\setminus E(T')$, prove that there is an edge $e' \in E(T') \setminus E(T')$ such that $T'+e-e'$ and $T-e+e'$ are both spanning trees of G.

My proof:

Let $n(G) = n$. Given $e \in E(T)\setminus E(T')$, call its endpoints $u$ and $v$. We know:

• $T'+e$ must have exactly one cycle. Call it $C$.
• $T-e$ has exactly 2 components. Call them $X$ and $Y$.

Now, $u$ and $v$ are part of $C$ in $T'+e$, so there must be one other $u,v$-path in $T'+e$ that does not include $e$. Specifically there must be one other edge $e'$ that joins $X$ and $Y$. This is the edge we are looking for, because:

• The removal of $e'$ from $T'+e$ breaks $C$, so $T'+e-e'$ is acyclic and has $n-1$ edges. Therefore $T'+e-e'$ is a spanning tree of G.
• The addition of $e'$ to $T-e$ connects $X$ and $Y$. Therefore $T-e+e'$ is connected and has $n-1$ edges. Therefore $T-e+e'$ is a spanning tree of G. $\square$

The key to my thinking is that fact that I can keep track of the vertices in $X$ and $Y$ no matter which subtree I am in. I had this question on a graph theory midterm and missed some of the reasoning, so I would really appreciate comments on this proof - is it correct? Is there are better way? Are there completely different proofs?

-

For the most part, your proof looks good to me. However, as every edge in a tree is a cut edge, your $e^{\prime}$ could very well be in $E(T)$. By this, I mean you don't provide a construction guaranteeing $e^{\prime} \not \in E(T)$.
Since $T \neq T^{\prime}$, we know that $E(T) \neq E(T^{\prime})$. So they differ by at least one edge. I'd use this to select your $e$ and $e^{\prime}$. Then apply your reasoning regarding cuts and cycles that you outlined above.
I think he did prove that $e'$ wasn't in $E(T)$. $e'$ is an edge that connects $X$ and $Y$, but there is only one edge in $E(T)$ connecting $X$ and $Y$: $e$. Hence as long as $e$ is not equal to $e'$, you know $e'$ isn't in $E(T)$, and his construction did ensure that $e$ was not $e'$. –  Alex Zorn Apr 10 '14 at 20:48