Let’s go back to the original motivation for the Minimum Spanning Tree Problem. We are giv...

Let’s 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 {le}, 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 le over all edges e in p.

Here’s a variant of Kruskal’s 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 Kruskal’s Algorithm would do as well.) On the other hand, if there is a u-v path in H, we let duv denote the length of the shortest such path; again, length is with respect to the values {le}.Weadd e to H if 31euv.

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 e 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