A finite graph is connected. A positive real number is assigned to each point. Each point is colored red or blue and at least one point is colored red. Show that, given a knowledge of (1) the points and edges of the graph, (2) the number assigned to each red point, and (3) for each blue point the average of the numbers for the points joined to it, one can find the number assigned to each point.

**Solution**

We use induction on the number n of blue points. Suppose there are m red points. The induction hypothesis is that for each blue point C there are non-negative real numbers c_{1}, c_{2}, ... , c_{m} with sum 1 which depend only on the graph (and not on the numbers assigned to the points) such that the number assigned to the point C is c_{1}a_{1} + c_{2}a_{2} + ... + c_{m}a_{m} where a_{i} are the numbers assigned to the red points. For n = 0 there is nothing to prove. For n = 1, suppose the blue point P is adjacent to k red points. Then we can take c_{i} = 1/k for points adjacent to P and 0 for points not adjacent to P.

So now suppose the result holds for n. Consider a graph with m red points and n+1 blue points. Since the graph is connected we can find a blue point P which is joined to at least one red point. Suppose P has the number x. If we change the color of P to red, then for each remaining blue point C we can find non-negative numbers c_{i} with sum 1 such that the number assigned to C is c_{1}a_{1} + ... + c_{m}a_{m} + c_{m+1}x. Suppose there are k points adjacent to P. Then kx = sum of numbers of adjacent points. If an adjacent point is blue, then its number is c_{1}a_{1} + ... + c_{m}a_{m} + c_{m+1}x for some non-negative c_{i} with sum 1. If an adjacent point is red then its number is a_{i} for some i. Note that this can also be regarded as a linear combination of a_{j} with non-negative coefficients having sum 1. So kx = b_{1}a_{1} + ... + b_{m}a_{m} + b_{m+1}x, where the b_{i} are non-negative and have sum k. There was at least one red neighbour, so b_{m+1} < k. Hence we can solve for x to get x = ∑ (b_{i}/(k - b_{m+1}) a_{i}. Note that each of the coefficients (b_{i}/(k - b_{m+1}) is non-negative and that their sum is 1. Now for any other blue point we have that the number is c_{1}a_{1} + ... + c_{m}a_{m} + c_{m+1}x = ∑ (c_{i} + c_{m+1}b_{i}/(k - b_{m+1}) a_{i}. Again each coefficient is non-negative and their sum is 1. So the induction is complete.

*Comment*

Note that we need the conditions c_{i} non-negative and ∑ c_{i} = 1 are needed to make the induction work. If we had the simpler hypothesis that the number for each blue point is a linear combination of the red numbers, then we could still change one blue point P with number x to red. But then we would have kx = sum of a_{i} joined to P + sum of numbers of blue points joined to P = (by induction) ∑ c_{i}a_{i} + hx. But if h = k, we get stuck at this point.

© John Scholes

jscholes@kalva.demon.co.uk

18 Sep 2002