\problemdata
{S00 ps4}
{graph}

\begin{problem}
Let $G=(V,E)$ be an undirected graph, and let $r:V\to\reals$ be a
function associating a real number with each vertex.  Suppose $r$
satisfies the property that for each $v\in V$ such that $v$ has at
least one neighbor, the value $r(v)$ is the average of the values of
$v$'s neighbors.  Prove that if the graph is connected, then
$r(u)=r(v)$ for all $u,v\in V$.

\solution{
Any non-empty, finite set of real numbers is totally-ordered, and thus
has a minimum element.  So for any function $r$, there must be a {\em
minimum vertex} $u$ such that for all vertices $v\neq u$, $r(u)\leq
r(v).$ Consider any valid function $r$ and a connected graph $G$.  Let
$u$ be a minimum vertex (which must exist).  Since $G$ is connected,
either $u$ is the only vertex (in which case the result follows
trivially), or $u$ must be adjacent to some non-empty set of nodes
$\{v_1,\dots\,v_k\}$, where $r(u)\leq r(v_i)$ for $i=1,\dots,k$.
Since $r(u)$ is the average of all $r(v_i)$ for $i=1,\dots,k$, then we
must have $r(u)=r(v_1)=\dots =r(v_k)$, implying that $v_1,\dots,v_k$
are all minimum vertices.
 
Therefore any minimum vertex must be adjacent to only minimum vertices.
Since $G$ is connected, this means that all vertices must be minimum vertices,
and thus $r(u)=r(v)$ for all $u,v\in V$.
\end{solution}
}
\end{problem}
