Let set of all spanning trees (not just minimum ones) of weighted, connected, undirected graph G = (V,E). Recall that adding edge e to spanning tree T creates unique cycle, and subsequently removing any other edge e0 6= e from this cycle gives back different spanning tree T0. We will say that T and T0 vary by single edge swap (e, e0) and that they are neighbors.

(a) Illustrate that it is possible to move from any spanning tree T to any other spanning tree T0 by performing series of edge-swaps, that is, by moving from neighbor to neighbor. At most how many edge-swaps are required?

(b) Illustrate that if T0 is an MST, then it is possible to select these swaps so that costs of spanning trees encountered along way are non-increasing. In other words, if sequence of spanning trees encountered is T = T0 ! T1 ! T2 ! Tk = T0; then cost(Ti+1)  cost(Ti) for all i < k.

(c) Let the following local search algorithm which is given as input undirected graph G. Let T be any spanning tree of G while there is edge-swap (e, e0) which reduces cost(T):
T T + e - e0
return T
Illustrate that this procedure always returns minimum spanning tree. At most how many iterations does it take?