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$.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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$?
answered Aug 13, 2017 at 22:44
-
$\begingroup$ How do we know that removing an edge from X results in cycle components? $\endgroup$– chesterAug 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$– chesterAug 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$– chesterAug 14, 2017 at 17:40