1. Let G = (V,E) be an undirected, connected graph with weight function w: E → R. Suppose that |E| ≥ |V| and that all the edge weights are distinct. Let be the set of all spanning trees of G, and let T be the minimum spanning tree of G. Then a second-best minimum spanning tree is a spanning tree T' such that w(T') = min{w(T"): T" ЄT\{T}}. (a) Show that the minimum spanning tree is unique, but that the second-best minimum spanning tree is not necessarily unique. (b) Let T be the minimum spanning tree of G. Prove that G contains some edge (u,v) = T and some edge (x, y) & T such that T \ {(u,v)} U {(x,y)} is a second-best minimum spanning tree of G. (c) Now let T be any spanning tree of G and for any two vertices (u, v) € V let max(u,v) denote an edge of maximum weight on the unique simple path between u and v in T. Describe an O(|V|2)-time algorithm that given T computes max(u, v) for all u, v € V. (d) Give an efficient algorithm to compute the second-best minimum spanning tree of G.

1. Let G = (V,E) be an undirected, connected graph with weight function w: E → R. Suppose that |E| ≥ |V| and that all the edge weights are distinct. Let be the set of all spanning trees of G, and let T be the minimum spanning tree of G. Then a second-best minimum spanning tree is a spanning tree T' such that w(T') = min{w(T"): T" ЄT\{T}}. (a) Show that the minimum spanning tree is unique, but that the second-best minimum spanning tree is not necessarily unique. (b) Let T be the minimum spanning tree of G. Prove that G contains some edge (u,v) = T and some edge (x, y) & T such that T \ {(u,v)} U {(x,y)} is a second-best minimum spanning tree of G. (c) Now let T be any spanning tree of G and for any two vertices (u, v) € V let max(u,v) denote an edge of maximum weight on the unique simple path between u and v in T. Describe an O(|V|2)-time algorithm that given T computes max(u, v) for all u, v € V. (d) Give an efficient algorithm to compute the second-best minimum spanning tree of G.