Reply
Wed 5 Oct, 2005 08:42 pm
Let T_1 and T_2 be spanning trees of a connected graph G.
(i) If e is any edge of T_1, show that there exists an edge f og T_2 such that the graph (T_1 - {e}) U {f} (obtained from T_1 on replacing e by f) is also a spanning tree.
(ii). Deduce that T_1 can be 'transformed' into T_2 by replacing the edges of T_1 one at a time by edges of T_2 in such a way that a spanning tree is obtained at each stage.