A weighted, undirected graph with n vertices and m edges is said to satisfy the triangle inequality if for every edge (u, v), the weight of (u, v) is less than or equal to the length of any other alternate path from u to v.
Prove that for such a graph, the total weight of all edges is <= (m-n+1)*MST, where MST is the total weight of all edges of the minimum spanning tree.
(Hint: What is the maximum possible weight of an edge of the graph that does not belong to the minimum spanning tree?)
Solving the hint
The weight of an edge that is not in the minimum spanning tree is less than or equal to MST (by the triangle inequality).
To see this, consider the case where the only other path from u to v is the whole of the minimum spanning tree. (Some other path must exist or else the edge would be in the minimum spanning tree, which is a contradiction.) Then, by the triangle inequality this edge's weight must be less than or equal to the weight of this alternate path, which is MST.
Attempt at the rest of the problem
There can be at most m-n+1 edges not in the spanning tree. (In a graph where there are the same number of nodes and edges, at most one edge is not in the MST).
The total weight of these edges is <= MST * (m-n+1). But then when you add the weight of the edges in the minimum spanning tree, you get that the sum of all the weights of the edges in the graph is <= MST * (m-n+2), which is not quite as tight as the bound that you wanted. So there must be another trick to the question.
