Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
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
I'd be willing to buy that. I think my approach is still a faster way to get the edges though. – ml0105 Apr 10 '14 at 20:55
But how did you actually select your e and e'? – mb7744 Apr 11 '14 at 0:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.