2. Graded Problem (Page limit: 1 sheet; 2 sides) This problem is on finding a Minimum width spanning tree Let G = (V, E, W) be a weighted connected (undirected) graph, where V is the set of vertices, E is the set of edges, we E W for each e E is a nonnegative weight of the edge e. A spanning tree is defined as usual, namely T = (V, TE) where TE E and T is a tree. The width of a spanning tree T is max(we l e E Tc) G if it is a spanning Thus it is the most "expensive" edge in the tree. T is a Minimum width spanning tree of tree and achieves the minimum width among all spanning trees of G Show that even if the weights of G = (V, E, W) are all distinct, there could be more than one Minimum width spanning trees. . Suppose E,-{e E E | we t} is the set of edges in G with weights at most t. Suppose Gt has connected components C1, C2,.. . Cs, for some s 21. Let T, be a Minimum width spanning tree of C (for 1