Lets go back to the original motivation for the Minimum Spanning Tree Problem. We are given a connected, undirected graph G = (V , E) with positive edge lengths {l_e}, and we want to find a spanning subgraph of it. Now suppose we are willing to settle for a subgraph H = (V , F ) that is denser than a tree, and we are interested in guaranteeing that, for each pair of vertices u, v ? V, the length of the shortest u-v path in H is not much longer than the length of the shortest u-v path in G. By the length of a path P here,we mean the sum of l_e over all edges e in P.

Heres a variant of Kruskals Algorithm designed to produce such a subgraph.

. First we sort all the edges in order of increasing length. (You may assume all edge lengths are distinct.)

. We then construct a subgraph H = (V , F ) by considering each edge in order.

. When we come to edge e = (u,v), we add e to the subgraph H if there is currently no u-v path in H. (This is what Kruskals Algorithm would do as well.) On the other hand, if there is a u-v path in H, we let d_uv denote the length of the shortest such path; again, length is with respect to the values {l_e}. We add e to H if 3(l_e) d_uv.

In other words, we add an edge even when u and v are already in the same connected component, provided that the addition of the edge reduces their shortest-path distance by a sufficient amount.

Let H = (V , F ) be the subgraph of G returned by the algorithm.

(a) Prove that for every pair of nodes u, v ? V, the length of the shortest u-v path in H is at most three times the length of the shortest u-v path in G.

(b) Despite its ability to approximately preserve shortest-path distances, the subgraph H produced by the algorithm cannot be too dense. Let f(n) denote the maximum number of edges that can possibly be produced as the output of this algorithm, over all n-node input graphs with edge lengths. Prove that

lim