Let C* be a set of edges of a graph G. Show that, if C* has an edge in common with each spanning forest of G, then C* contains a cutset.

 

Obtain a corresponding result for cycles.

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.

You're going to have to post some kind of problem with your version of the proof before we help out