# Spanning Trees: Prove if $e_1$ is an edge in $X$ that isn't in $Y$, then there exists an edge …

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

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$?
• I use $C_i$ to denote component, not cycle components.... perhaps let me change the notaiton to $T_i$. – Siong Thye Goh Aug 14 '17 at 17:29
• 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? – chester Aug 14 '17 at 17:31
• but do we know an $e_2$ that is in $Y$, ($Y$ is a spanning tree) will connect $T_1$ and $T_2$? – Siong Thye Goh Aug 14 '17 at 17:38