Consider the following algorithm. Sort the weights in decreasing order. Let these edges be e1, e2, . . . , em so that w(ei) w(ei+1). For j = 1 to m if the removal of ej does not give a disconnected graph, remove ej from the solution. Show by induction that in any stage of this algorithm the graph contains a spanning tree. Deduce that this algorithm finds a minimum spanning tree.