= Solution
Let $(\mathcal F_n)$ be the <natural filtration> of the <random walk on a graph>. For a bounded <harmonic function on a graph>, the transition rule and the <Markov property> give
$$
\mathbb E[h(X_{n+1})\mid\mathcal F_n]
=\frac1{\deg(X_n)}\sum_{u\sim X_n}h(u)=h(X_n).
$$
Thus $h(X_n)$ is a bounded <martingale>. The <martingale convergence theorem> gives a finite almost sure limit $L$.
On the probability-one recurrence event, every vertex $v$ is visited along a sequence $n_k\to\infty$. Along that sequence $h(X_{n_k})=h(v)$, while convergence of the whole sequence forces $h(v)=L$. Therefore every pair of vertices has the same value. This is the <bounded harmonic function theorem on a recurrent graph>:
$$
\boxed{h(v)=h(w)\quad\text{for all vertices }v,w.}
$$
\b[Recurrence makes each vertex value a subsequential limit of the same convergent martingale.] A connected <locally finite graph> is countable, since it is the union of its finite distance balls, so these almost sure assertions can also be combined by a countable intersection. The one-vertex case is immediate.
Back to article page
