Sum of squares of minimum spanning tree

108 Views Asked by At

Let $T$ be a minimum spanning tree of connected graph $G=(V,E)$ with respect to some weight function $w:E\to (0,\infty)$.

To prove or disprove that the sum of squares of function $w$ values on edges $T$ is minimal.

In another words, there is no spannig tree $T'$ such that $$ \sum_{e\in T'} w(e)^2<\sum_{e\in T} w(e)^2. $$

I try to prove this by $$ \left(\sum_{i}a_{i}\right)^{2}=\sum_{i}a_{i}^{2}+2\sum_{_{i<j}}a_{i}a_{j} \;\implies\; \sum_{i}a_{i}^{2}= \left(\sum_{i}a_{i}\right)^{2}-2\sum_{_{i<j}}a_{i}a_{j}. $$

Since $T$ is a minimum spanning tree I conclude that $(\sum_{i}a_{i})^{2}\leq(\sum_{i}a'_{i})^{2}$.

I have a problem to prove that $2\!\sum_{_{i<j}}a_{i}a_{j}\leq2\!\sum_{_{i<j}}a'_{i}a'_{j}$ (I am really not sure about this fact).

Help is welcome.

1

There are 1 best solutions below

0
On

Begin by proving that the minimum spanning tree is only affected by the relative ordering of the edges, not by the actual values of the weight function. This follows if you assume the correctness of some algorithm that only operates on the weights by comparing them, and not by doing any fancy arithmetic.

For positive weights, if we sort the edges in ascending order such that $$w(e_1) \le w(e_2) \le \dots \le w(e_m)$$ then their squares are also sorted in ascending order with $$w(e_1)^2 \le w(e_2)^2 \le \dots \le w(e_m)^2$$ and vice versa, so the relative order of edges does not change and hence the minimum spanning tree (or set of minimum spanning trees, when there are ties) does not change.