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, w E W for each e 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 TE} Thus it is the most "expenive" edge in the tree. T is a Minimum width spanning tree of G if it is a spanning 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 Est {e& E I ue-t} is the set of edges in G with weights at most t. Suppose G-t has connected components C1, C2,... .Cs, for some s 1. Let T, be a Minimum width spanning tree of Ci (for 1 SiS s), prove that there is a Minimum width spanning tree T of G that contains U1T i.e.. T is obtained by adding some number of (zero or more) edges from E to the edge sets of TI. T- T, . Can you write down what is the number of edges to be added (in terms of the data already given)? Suppose w