2
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

Hint:

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$?

$\endgroup$
  • $\begingroup$ How do we know that removing an edge from X results in cycle components? $\endgroup$ – chester Aug 14 '17 at 17:20
  • $\begingroup$ I use $C_i$ to denote component, not cycle components.... perhaps let me change the notaiton to $T_i$. $\endgroup$ – Siong Thye Goh Aug 14 '17 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 '17 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$ – Siong Thye Goh Aug 14 '17 at 17:38
  • $\begingroup$ I want to say yes. But I am confused as to why. $\endgroup$ – chester Aug 14 '17 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.