Let T be a tree with vertex set {v1, v2, . . . , vn}, and a weight wij on edge vivj .
(a) Prove that it’s possible to put a number on every vertex such that each weight wij is
the sum of the numbers on vertices vi and vj .
(Hint: induct on the number of vertices in T.)
(b) Prove that there are weighted graphs for which this is not possible.