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?

  • $\begingroup$ They also need to be with the same weight. $\endgroup$
    – nir shahar
    Oct 1 at 7:10
  • $\begingroup$ @nirshahar: Do you mean that $a$ and $b$ need to have the same weight? $\endgroup$
    – Rob32409
    Oct 1 at 7:12
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Oct 1 at 7:15
  • $\begingroup$ @nirshahar: They are only spanning trees. $\endgroup$
    – Rob32409
    Oct 1 at 7:17
  • 2
    $\begingroup$ 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 $\endgroup$ Oct 1 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.