Can someone please verify my proof or offer suggestions for improvement?

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

Let $e = \{x, y\}$. There exists a path $x, u_1, u_2, \ldots u_k, y$ in $T'$. There exists an edge $e' = \{u_d, u_{d+1}\}$ such that $e' \notin T$. If that weren't the case, then the union of $x, y$ and $x, u_1, u_2, \ldots u_k, y$ would form a closed path. Remove edge $e'=\{u_d, u_{d+1}\}$ and add edge $\{x,y\}$ to $T'$. Then, the graph $T'+e-e'$ is connected. To see this, let $\alpha$ and $\beta$ be two vertices in $G$. There exists a path $p$ in $T'$ from $\alpha$ to $\beta$. If $p$ includes $\{u_d, u_{d+1}\}$, form a path $p'$ in $T'+e-e'$ by deleting $u_d, u_{d+1}$, and inserting $u_{d+1}, u_{d+2}, \ldots, x, u_1, u_2, \ldots u_{d-1}, u_d$ in its place. Then, the new path connects $\alpha$ to $\beta$ in $T'+e-e'$. Since $T'+e-e'$ contains $n$ vertices and $n-1$ edges and is connected, it is a spanning tree.

Using similar reasoning, it can be shown that $T-e+e'$ is a spanning tree.


1 Answer 1


It's seems legitimate. Here's some feedback.

  • I suggest "There exists a path $x, u_1, u_2, \ldots u_k, y$ in $T'$." be prefaced with "Since $e \not\in E(T')$, ..." or maybe "Since $T'$ is a tree...".

  • I try to avoid structures like "[Claim] is true. This is because...." because the reader can be left thinking Why is [Claim] true? without realizing that it's proved in the next sentence.

    I feel these can be improved by using "[Claim] is true, otherwise ..." or "[Claim] is true (otherwise ...)." or "If [Claim] is false, then [contradiction]. So [Claim] is true."

    E.g. "Then, the graph $T'+e-e'$ is connected. To see this, ..."

    E.g. "There exists an edge $e' = \{u_d, u_{d+1}\}$ such that $e' \notin T$. If that weren't the case, ...". This statement also has the disadvantage of not including the edges $\{x,u_1\}$ and $\{u_k,y\}$.

    Consequently, it might be better to define $P$ as the path $x, u_1, u_2, \ldots u_k, y$, and say "If $P$ is completely contained in $T$, then $P \cup e$ is a cycle in $T$, contradicting the assumption that $T$ is a tree. Hence there is some edge $e' \in P$ that's not in $T$."

  • Where did $G$ come from? It should be $T'$?

  • $p'$ might not be a path (it might reuse edges and vertices), but would be a walk.

  • "$u_{d+1}, u_{d+2}, \ldots, x, u_1, u_2, \ldots u_{d-1}, u_d$" should be "$u_{d+1}, u_{d+2}, \ldots, u_k, y, x, u_1, u_2, \ldots u_{d-1}, u_d$". And isn't it backwards?

  • Rather than "Using similar reasoning...", we can apply the proof with $T$ and $T'$ swapped to complete the full proof.

  • $\begingroup$ Thanks again! Your comments were very helpful. I'll keep them in mind when I next write a proof. $\endgroup$
    – user154185
    Jul 5, 2014 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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