Consider a connected graph G = (V, E) where each edge has a non-zero positive weight. Furthermore, assume that all edge weights are distinct. Using the cut property, first show that that for each vertex v V , the edge incident to v with minimum weight belongs to a Minimum Spanning Tree (MST). Can you use this to devise an algorithm for MST - the above step identifies at least |V |/2 edges in MST - you can collapse these edges, by identifying the vertices and then recursively apply the same technique - the graph in the next step has at most half of the vertices that you started with - and so on. What is the running time of your algorithm? Note that for an edge e = uv in the graph G = (V, E), identifying vertex u with v or collapsing e is the following operation: Replace the vertices u and v by a new vertex, say u 0 . Remove the edge between u and v. If there was an edge from u (respectively, v) to any vertex w (w 6= u and w 6= v), then we add an edge (with the same weight as of edge uw (respectively, vw)), between the vertices u 0 and w. This transforms graph G to a new graph G0 = (V 0 , E0 ), where |V 0 | < |V | and |E 0 | < |E|. Note that G0 may be a multigraph (i.e., between a pair of vertices, there may be more than one edge). For example, if uv, uw, and vw are edges in G, then G0 will have two edges between u 0 and w when we identify u with v. We can transform G0 to a simple graph by keeping the edge with the lower weight among uw and vw as the representative for u 0w for the computation of MST.