Say $X$ and $Y$ are two different spanning trees of a simple and connected and undirected graph $G$. Prove that if $e_1$ is an edge in $X$ that isn't in $Y$, then there exists an edge $e_2$ in $Y$ that isn't in $X$... so the graph $(X − e_1) + e_2$ (obtained from $X$ on replacing $e_1$ by $e_2$) is also a spanning tree of the original graph, $G$.


1 Answer 1



Upon removing $e_1$, the graph $X-e_1$ is disconnected into two components, $T_1$ and $T_2$.

Think of the edges of $Y$, must there be one that connects a vertex in $T_1$ and a vertex in $T_2$?

  • $\begingroup$ How do we know that removing an edge from X results in cycle components? $\endgroup$
    – chester
    Aug 14, 2017 at 17:20
  • $\begingroup$ I use $C_i$ to denote component, not cycle components.... perhaps let me change the notaiton to $T_i$. $\endgroup$ Aug 14, 2017 at 17:29
  • $\begingroup$ I see! Thanks. As for your question, we don't necessarily know that an edge $e_2$ that isn't in X will connect $T_1$ and $T_2$, do we? $\endgroup$
    – chester
    Aug 14, 2017 at 17:31
  • $\begingroup$ but do we know an $e_2$ that is in $Y$, ($Y$ is a spanning tree) will connect $T_1$ and $T_2$? $\endgroup$ Aug 14, 2017 at 17:38
  • $\begingroup$ I want to say yes. But I am confused as to why. $\endgroup$
    – chester
    Aug 14, 2017 at 17:40

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.