In Kruskal's algorithm, we sort edges from least weight to greatest weight and add the edge if and only if both endpoints are in different connected components in current iteration.
Now the question is follows: Our goal is to construct a subgraph in a connected weighted undirected graph such that the distance between any two vertices in the new graph are at most 5 times of that in the original graph. Also, we want to make the graph sparse.
Some time ago my instructor said we can use the following algorithm: We iterate edges from least weight to greatest weight like Kruskal's and add the edge if and only if both endpoints are not connected or current distance between the two vertices are strictly greater than 5 times of the edge weight. (We assume all edge weights are strictly positive, and distance is the sum of weight of edges on that path as usual)
I know how to show this new graph has the property that the distance between any two vertices in the new graph are at most 5 times of that in the original graph. The question is, how to show when $n$ goes to infinity, let $l(n)$ be the maximum number of edges selected by the algorithm among all graphs with $n$ vertices and all possible (strictly positive) edge weights. Show $\lim_{n\to +\infty}\frac{l(n)}{n^2} = 0$. That is, the graph would be way much sparse than complete graph. Does anyone have good reference to this problem?
