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.)
To prove that it is possible to assign a number to every vertex in a graph such that each weight between two vertices is the sum of the numbers assigned to those vertices, we can use induction on the number of vertices in the graph.
Let's assume we have a graph with n vertices. We will prove that it is possible to assign numbers to the vertices such that the weight between any two vertices is the sum of the numbers assigned to those vertices.
1. Base Case:
When n = 2, we have two vertices v1 and v2. We can assign any two numbers, let's say a and b, to v1 and v2 respectively. The weight wij between v1 and v2 will be a + b, which satisfies the condition.
2. Inductive Step:
Assume that for any graph with k vertices, where k ≤ n, it is possible to assign numbers to the vertices satisfying the condition. Now, we need to prove that it is also possible for a graph with (k+1) vertices.
Consider a graph T with (k+1) vertices. Remove any vertex v from T to obtain a subgraph with k vertices. By the induction hypothesis, we can assign numbers to the k vertices such that the weight between any two vertices in the subgraph is the sum of the assigned numbers.
Now, add the removed vertex v back to the graph. To ensure that the weight between v and any other vertex in the graph is the sum of the assigned numbers, we can assign a number x to v such that x is the sum of the numbers assigned to the vertices in the subgraph.
By adding the vertex v with the assigned number x, we have constructed a graph with (k+1) vertices where each weight between two vertices is the sum of the assigned numbers. This completes the inductive step.
Therefore, by mathematical induction, we have proven that it is possible to assign numbers to the vertices of any graph such that each weight between two vertices is the sum of the assigned numbers.