Back to the 2022 paper

Module 5: Graphs and Trees

20225m

Suppose that T1T_1 and T2T_2 are spanning trees of a simple graph GG. Moreover, suppose that e1e_1 is an edge in T1T_1 that is not in T2T_2. Show that there is an edge e2e_2 in T2T_2 that is not in T1T_1 such that T1T_1 remains a spanning tree if e1e_1 is removed from it and e2e_2 is added to it, and T2T_2 remains a spanning tree if e2e_2 is removed from it and e1e_1 is added to it.

Similar questions