$T=T_1-f_1+f_2$ is a spanning tree

34 Views Asked by At

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ spanning trees in $G$ with $F_1\cap F_2=\emptyset.$ 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.
My idea:
Let $f_1\in F_1$. Because of $F_1\cap F_2=\emptyset$ there exists $f_2\in F_2\backslash F_1$ so that adding $f_2$ to $F_1$ yields a cycle in $T_1$ containing $f_1$ and $f_2$. So if we remove $f_1$, $T=T_1-f_1+f_2$ is connected with $|V|-1$ edges and is a spanning tree. Is my idea correct?