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?
6
-
$\begingroup$ They also need to be with the same weight. $\endgroup$– nir shaharCommented Oct 1, 2021 at 7:10
-
$\begingroup$ @nirshahar: Do you mean that $a$ and $b$ need to have the same weight? $\endgroup$– Rob32409Commented Oct 1, 2021 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 shaharCommented Oct 1, 2021 at 7:15
-
$\begingroup$ @nirshahar: They are only spanning trees. $\endgroup$– Rob32409Commented Oct 1, 2021 at 7:17
-
3$\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$– Hendrik JanCommented Oct 1, 2021 at 11:33
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
You want to prove a false statement. Its possible that T -{a} + {b} is not spanning tree. Consider the below example
Lets say T1 is-
1
/ \
2 3
/ /
5 4
/
6
Lets say T2 is-
1
\
2 3
/|\ /
5 6 4
both are spanning tree but if we replace edge 1-2 in T1 with edge 2-6 in T2 then it will not be spanning tree anymore. QED
-
$\begingroup$ It will still be a spanning tree with that replacement… However, it will not if you replace egde $\{5,6\}$ in $T_1$ with edge $\{2,4\}$ in $T_2$. $\endgroup$ Commented Dec 27, 2021 at 15:12
-
$\begingroup$ I made a mistake. I corrected it. actually you need to replace 1-2 with 2-6 $\endgroup$ Commented Dec 28, 2021 at 12:32