2
$\begingroup$

Please help with the following homework problem:

Let G be an undirected graph, $v: E\to R$ and $w: E\to R$ be two weight functions on the edges of $G$. Let $z: E\to R$ be defined as the sum of $v$ and $w$, i.e. for every edge $e$ of $G$ $z(e)=v(e) + w(e)$. Let $V$, $W$, and $Z$ be the total weights of the minimum weight spanning trees of $G$ with respect to weight functions $v$, $w$ and $z$, respectively. Prove or disprove: $Z \geq V+W$.

After trying a few graphs, I am convinced the that no counter example exists and that the statement is true. Please help me get started on the proof.

1 Answers 1

5

If this $Z \lt V + W$, then consider the the minimum weight spanning tree for which Z is attained. Let its weight according to v be V' and according to w be W'. $V' + W' \lt V + W$, so either V' < V or W' < W, which is not possible as V and W are the weights for the minimum spanning trees for v and w, respectively.