= Solution
A <self-avoiding walk> is a finite sequence of <graph vertices> $v_0,\ldots,v_n$ in which successive vertices are adjacent and no <graph vertex> is repeated; its length is $n$, the number of <edges>. Include the zero-length walk.
Split a length-$m+n$ walk from $v$ into its first $m$ <edges> and remaining $n$ <edges>. After fixing the first segment, the number of possible suffixes is at most $\sigma_n$, since forgetting the prohibition on revisiting its earlier vertices can only increase that number. Thus $\sigma_{m+n}(v)\leq\sigma_m(v)\sigma_n$, and taking the supremum gives
$$
\boxed{\sigma_{m+n}\leq\sigma_m\sigma_n}.
$$
Every finite-radius ball is finite because degrees are bounded. An infinite connected <graph> has vertices arbitrarily far from each root, so shortest paths give $\sigma_n(v)\geq1$. Also $\sigma_n\leq\Delta(\Delta-1)^{n-1}$ for $n\geq1$: after the first <edge>, an immediate reversal is forbidden. In particular $\Delta\geq2$ and these suprema are finite.
Apply the <Fekete lemma>: a real <subadditive sequence> $a_{m+n}\leq a_m+a_n$ satisfies $\lim a_n/n=\inf_{n\geq1}a_n/n$, allowing negative infinity. Here $a_n=\log\sigma_n\geq0$, so the limit is finite. The <uniform connective constant of a bounded-degree graph> is therefore
$$
\boxed{\mu=\lim_{n\to\infty}\sigma_n^{1/n}=\inf_{n\geq1}\sigma_n^{1/n},\qquad1\leq\mu\leq\Delta-1}.
$$
Back to article page
