<p>If the weight of the MST is $W$, then the weight of all edges is $\le \binom n 2 \cdot W$, because every edge in the graph is bounded by the unique path in the MST connecting the two nodes of the edge by the triangle inequality.</p>

<p>This is tight: Consider a line with edge weights all being equal to $1$ and let the metric be the shortest path metric induced by this line. Then the MST is this line and has weight $n-1$, on the other hand there are $\Omega(n^2)$ pairs of nodes with a distance of $\Omega(n)$.</p>

CC BY-SA 3.0
2011-04-15T21:12:13.613Z
2011-04-15T21:12:13.613Z
5501
<p>I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum spanning tree). Also if anyone of you can post some lecture note or paper links so that i can study these graphs.</p>

CC BY-SA 3.0
2011-04-15T20:01:40.157Z
Less cryptography in the title, please.
Dave Clarke
<graph-theory><co.combinatorics><graph-algorithms><metrics>
Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST
singhsumit
# Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST

(Asked by: username_0 on 2011-04-15)

I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum spanning tree). Also if anyone of you can post some lecture note or paper links so that i can study these graphs.

**Tags:** graph-theory, co.combinatorics, graph-algorithms, metrics
> **Comments:**
> **username_1**: Less cryptography in the title, please.  

---

## 1 answers

### Answer by username_2 on 2011-04-15. Score: 3 | Accepted answer

If the weight of the MST is $W$, then the weight of all edges is $\le \binom n 2 \cdot W$, because every edge in the graph is bounded by the unique path in the MST connecting the two nodes of the edge by the triangle inequality.

This is tight: Consider a line with edge weights all being equal to $1$ and let the metric be the shortest path metric induced by this line. Then the MST is this line and has weight $n-1$, on the other hand there are $\Omega(n^2)$ pairs of nodes with a distance of $\Omega(n)$.


---

