# Removing and adding edges from spanning tree

Let $$T_1$$ and $$T_2$$ be two spanning trees. If $$a$$ is an edge in $$T_1$$ that is not in $$T_2$$, and $$b$$ is an edge in $$T_2$$ that is no in $$T_1$$. I want to prove that $$T_1 - \{ a\} + \{ b\}$$ is a spanning tree. I have an idea of what is happening but I don't know exactly how to write the proof. I know that $$T_1 - \{ a\}$$ creates a partition of the vertices, but how can I conclude that adding $$b$$ to $$T_1 - \{ a\}$$ is necessarily a spanning tree?

• They also need to be with the same weight. Oct 1 at 7:10
• @nirshahar: Do you mean that $a$ and $b$ need to have the same weight? Oct 1 at 7:12
• Are you asking about spanning trees or about minimal spanning trees? If they are minimal then this would be a requirement. Otherwise, it is not necessary. Oct 1 at 7:15
• @nirshahar: They are only spanning trees. Oct 1 at 7:17
• The proper formulation is probably: if $a$ is in $T_1 \setminus T_2$ then there exists $b$ in $T_2\setminus T_1$ such that $T_1-a+b$ is a spanning tree. This "basis exchange property" holds for both spanning trees in general as for minimal spanning trees. Related: Edge exchange property of two Minimum Spanning Trees Oct 1 at 11:33