This problem is generalization of this one. Suppose $G$ is a graph and $S\subset V(G)$. Suppose we have arbitrarily assign real numbers to each element of $S$. Prove that we can assign numbers to each vertex in $G\backslash S$ that for each $v\in G\backslash S$ number assigned to $v$ is average of its neighbors.
Problem
Source: Iran TST 2004
Tags: combinatorics proposed, combinatorics
11.08.2006 00:39
I wanted to post this generalization after seeing these problems: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=468314#p468314 http://www.artofproblemsolving.com/Forum/viewtopic.php?p=468314#p468314 If $S$ does not meet every connected component of $G$, then it's easy to take care of the components disjoint from $S$: just assign the value $0$ to each point in such a component. This means that it suffices to restrict our attention to the case when $S$ does meet every component, and in this case the proof in that first link works, with only the obvious modifications (that last argument in that topic basically says that in that particular case, $S$ meets every component; since here we're already assuming this, no such argument is needed).
09.06.2019 18:52
Let $T = V(G) / S.$ We interpret the desired labelling as a system of equations. Consider the adjacency matrix $A$ of the vertices in $T$, with the one difference that we write $-deg(v_i)$ along the main diagonal. In this way, the problem's condition can be interpreted as: $$A \cdot v = v',$$ where $v$ is the vector of the labellings of the elements of $T$, and $v'$ is some fixed vector. We need to show that this has a solution. First of all, as grobber did above, we can WLOG assume that there is no connected component in which $S$ contains no elements. With this assumption, we're ready to show that the rows of $A$ are linearly independent. Indeed, suppose that they were not for contradiction. Then, if we let $r_i$ be the vector corresponding to the $i$th row of $A$, then there exist real numbers $x_i$ so that $$\sum x_ir_i = 0.$$To see that this cannot occur, consider the largest $x_i.$ Then since $-x_ideg(v_i)$ must be summed with other terms to make the $i$th coordinate zero, we know that all neighbors $v_j$ of $v_i$ must be in $T$, and have $x_j = x_i.$ If we continue this logic, we get that the connected component of the subgraph of $G$ spanned by $T$ which contains $x_i$ is adjacent to no vertices of $S$, i.e. it should've been removed by the above assumption, contradiction. $\square$
10.06.2019 15:13
Another approach. The idea is at first to assign some number to each vertex of $V(G)\setminus S$ and then iterate assigning to each vertex of $V(G)\setminus S$ the average of its neighbours. If the corresponding real sequences, obtained for each vertex, converge then their limits will do the job. It's not certain that each initial assigning will bring convergence, it's even not true, but we show it holds for a specific initial assignment. To begin with, it's enough to prove the claim when all numbers assigned to $S$ are non negative. Indeed, in general case, we can represent each number in $S$ as difference of non negative numbers, then get missing numbers to both configurations and finally subtract vertex-wise corresponding values. So, we may assume the assigned numbers to $S$ are non negative. Let $M$ be the maximal number assigned to $S$. By $v^{k}_j$ we denote the number assigned to the vertex $v_j\in V$ at step $k$. We set the initial assigning as $v^{(0)}_j:=M\,,\,\forall j,v_j\notin S $. We construct inductively the sequence $v^{k}_j, k=1,2,\dots$ $$ (*)\,\,\,\,\,\,\,\, v^{(k+1)}_j:= \begin{cases} \displaystyle \frac{1}{|N(v_j)|} \sum_{v_i\in N(v_j)} v^{(k)}_i\,,& v_j\notin S\\ v^{(k)}_j\,,& v_j\in S \end{cases} $$where $N(v_j)$ denotes the set of verticies adjacent to $v_j$ . Clearly $v^{(1)}_j\leq v^{(0)}_j\,,\,\forall v_j\in V$. Now, by induction, applying $(*)$, we conclude $v^{(k+1)}_j\leq v^{(k)}_j\,,\,\forall v_j\in V;k=0,1,\dots$ . It means the sequence $v^{(k)}_j$ for fixed $j$ and $k=0,1,\dots$ is monotonically decreasing and non negative, hence it converges to $v^*_j$. Finally, taking the limit in $(*)$, we conclude the assignment $v^*_j$ satisfies the requirement.