Minimum Spanning Tree over Vertices Proof

Question

This is the problem:

$d_{T}(v)$ denotes the degree of a vertex in a spanning tree $T$ and $w: V \rightarrow R^+$ is a weight function defined on vertices.

The goal is an algorithm that finds a spanning tree which minimizes the value $\sum_{v \in V}{d_{T}(v)*w(v)}$.

My idea is to define a new weight function on edges in the following way: $m(e_{ij})=w(v_i)+w(v_j)$, i.e. the weight of each edge is the weight of both of its vertices.

Then we run Kruskal on a graph with the given $m$ weight function. The problem is that I have no idea how to prove that it works.

I thought about starting with the expression $min \sum_{e \in E}{m(e)}$ which Kruskal yields, and then somehow change the summation to be over vertices. How can it be done?

Thanks!

Answer 1

It doesn't matter which minimum spanning tree algorithm you use. All you need to notice is that for a tree $T$, $$ \begin{align*} \sum_{(i,j) \in T} m(e_{ij}) &= \sum_{(i,j) \in T} w(v_i) + w(v_j) \\ &= \sum_i \sum_{(i,j) \in T} w(v_i) + \sum_j \sum_{(i,j) \in T} w(v_j) \\ &= 2 \sum_i d_T(i) w(v_i). \end{align*} $$ You take it from here.