Grinberg-Introduction-Graph-Theory · Problem 5.8

Trees and arborescences

Mathematics — Graph Theory · spanning-trees-exchange

Problem

Let GG be a connected multigraph. Let T1T_1 and T2T_2 be two spanning trees of GG. Prove the following: ((a)) For any e∈E(T1)∖E(T2)e \in E(T_1) \setminus E(T_2), there exists an f∈E(T2)∖E(T1)f \in E(T_2) \setminus E(T_1) with the property that replacing ee by ff in T1T_1 (that is, removing the edge ee from T1T_1 and adding the edge ff) results in a spanning tree of GG. ((b)) For any f∈E(T2)∖E(T1)f \in E(T_2) \setminus E(T_1), there exists an e∈E(T1)∖E(T2)e \in E(T_1) \setminus E(T_2) with the property that replacing ee by ff in T1T_1 (that is, removing the edge ee from T1T_1 and adding the edge ff) results in a spanning tree of GG. [Hint: The two parts look very similar, but (to my knowledge) their proofs are not.]

Related theory

Browse the problem library