Proof about spanning tress in graphs

38 Views Asked by At

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$.

Let $f_1 \in F_1$.

Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.

1

There are 1 best solutions below

2
On BEST ANSWER

If f1 is in F2 then take f2 = f1. EDIT as Casteels pointed out, this is ruled out by the wording of the question.

Else, T1 - f1 has two connected components say C1 and C2. T2 must have at least one edge from C1 to C2. Take that as f2.