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.
To prove the statement, let's proceed with an inductive argument.
(a) Base case: When T has only two vertices (n = 2), we can take the number 0 and 1 for the two vertices v1 and v2. Then the weight w12 is the sum of the numbers on v1 and v2, which is 0 + 1 = 1. Therefore, the statement is true for n = 2.
(b) Inductive assumption: Assume that the statement is true for any tree with k vertices, where k ≥ 2.
Inductive step:
Consider a tree T with (k + 1) vertices. Choose an arbitrary leaf node, let's say v1, and remove it along with its incident edge from the tree T. This leaves us with a new tree T' with k vertices.
By the inductive assumption, it is possible to assign numbers on the vertices of T' such that the sum of the numbers on any two vertices vi and vj is equal to the weight wij of the edge connecting them in T'.
Now, to construct the number assignment for T with (k + 1) vertices, we assign the number 0 to the vertex v1 (the one we removed earlier) and assign the remaining numbers on the vertices of T' as they were assigned in the previous step.
Since v1 is a leaf node, it is connected to a single vertex vj in T', and the weight w1j is the sum of the numbers on v1 and vj, which is 0 + nj (nj denotes the number on vertex vj in T'). Hence, the weight w1j is equal to the number nj.
Thus, we have successfully assigned numbers on the vertices of T such that each weight wij is the sum of the numbers on vertices vi and vj.
Therefore, by the principle of mathematical induction, the statement holds for all trees with any number of vertices.
For part (b), consider a weighted graph where an edge has a weight that is not equal to the sum of the numbers on its two vertices. For example, consider a graph with two vertices v1 and v2, and an edge between them with weight 2. If we assign 1 to v1 and 2 to v2, the sum of the numbers on the vertices v1 and v2 is 1 + 2 = 3, which is not equal to the weight of the edge (2). Hence, for certain weighted graphs, it is not possible to assign numbers on vertices satisfying the given condition.