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.