Local Search for Minimum Spanning Trees Consider the set of all spanning trees (not just minimum ones) of a weighted, connected, undirected graph G...

1. Local Search for Minimum Spanning TreesConsider the set of all spanning trees (not just minimum ones) of a weighted, connected, undirectedgraph G = (V,E). Recall that adding an edge e to a spanning tree T creates an unique cycle, andsubsequently removing any other edge e0 6= e from this cycle gives back a different spanning tree T0.We will say that T and T0 differ by a single edge swap (e, e0) and that they are neighbors.(a) Show that it is possible to move from any spanning tree T to any other spanning tree T0 byperforming a series of edge-swaps, that is, by moving from neighbor to neighbor. At most howmany edge-swaps are needed?(b) Show that if T0 is an MST, then it is possible to choose these swaps so that the costs of thespanning trees encountered along the way are non-increasing. In other words, if the sequence ofspanning trees encountered is T = T0 ! T1 ! T2 ! Tk = T0; then cost(Ti+1) cost(Ti) for alli < k.(c) Consider the following local search algorithm which is given as input an undirected graph G.Let T be any spanning tree of Gwhile there is an edge-swap (e, e0) which reduces cost(T):T + e − e0return TShow that this procedure always returns a minimum spanning tree. At most how many iterationsdoes it take?