[proofplan]
We compare the number of admissible words in the sofic shift with the number of directed paths in the presenting graph. Right-resolvingness gives a uniform bound on the size of each fibre of the label map from paths to words, while essentiality ensures that every finite graph path contributes a word appearing in a bi-infinite point of the shift. Thus word growth and path growth have the same exponential rate. Perron--Frobenius theory for finite non-negative matrices then identifies the exponential growth rate of paths with the spectral radius of the adjacency matrix.
[/proofplan]
[step:Define the language and the path-counting functions]
For each $m\in\mathbb{N}$, let $\mathcal{L}_m(Y)\subseteq \mathcal{A}^m$ denote the set of length-$m$ words appearing in some point of $Y$. The topological entropy of the subshift $Y$ is
\begin{align*}
h_{\mathrm{top}}(\sigma|_Y)=\lim_{m\to\infty}\frac{1}{m}\log |\mathcal{L}_m(Y)|.
\end{align*}
This limit exists by submultiplicativity of the language-counting sequence.
Let $\mathcal{P}_m$ denote the finite set of directed paths in $\mathcal{G}$ with exactly $m$ edges. Define the path-counting function
\begin{align*}
P_m:\mathbb{N}\to\mathbb{N}, \qquad m\mapsto |\mathcal{P}_m|.
\end{align*}
If $\mathbf{1}\in\mathbb{R}^{V}$ denotes the column vector with every coordinate equal to $1$, then
\begin{align*}
P_m=\mathbf{1}^{\top}M^m\mathbf{1}.
\end{align*}
Indeed, the $(u,v)$-entry of $M^m$ counts directed paths of length $m$ from $u$ to $v$, and summing over all ordered pairs $(u,v)\in V\times V$ counts all length-$m$ paths.
[/step]
[step:Compare words with paths using right-resolvingness]
Define the label map on length-$m$ paths by
\begin{align*}
\Lambda_m:\mathcal{P}_m\to\mathcal{A}^m
\end{align*}
by
\begin{align*}
\Lambda_m(e_1,\dots,e_m):=\ell(e_1)\cdots \ell(e_m).
\end{align*}
Since $\mathcal{G}$ is essential, every finite path in $\mathcal{G}$ occurs as a subpath of some bi-infinite path in $\mathcal{G}$. To justify this, let $p=(e_1,\dots,e_m)$ be a finite path with initial vertex $u$ and terminal vertex $v$. Essentiality gives a bi-infinite path passing through $u$, so taking its left half up to $u$ gives a left-infinite path ending at $u$. Essentiality also gives a bi-infinite path passing through $v$, so taking its right half starting at $v$ gives a right-infinite path beginning at $v$. Concatenating the left-infinite path, $p$, and the right-infinite path gives a bi-infinite path containing $p$. Hence every word in $\Lambda_m(\mathcal{P}_m)$ appears in a point of $Y$, so
\begin{align*}
\Lambda_m(\mathcal{P}_m)\subseteq \mathcal{L}_m(Y).
\end{align*}
Conversely, every word in $\mathcal{L}_m(Y)$ is read along some length-$m$ path in $\mathcal{G}$, so
\begin{align*}
\mathcal{L}_m(Y)\subseteq \Lambda_m(\mathcal{P}_m).
\end{align*}
Therefore
\begin{align*}
\mathcal{L}_m(Y)=\Lambda_m(\mathcal{P}_m).
\end{align*}
For each word $w\in\mathcal{L}_m(Y)$ and each starting vertex $v\in V$, right-resolvingness implies that there is at most one path in $\mathcal{P}_m$ starting at $v$ and labelled by $w$. Thus each fibre $\Lambda_m^{-1}(\{w\})$ has cardinality at most $|V|$. Hence
\begin{align*}
|\mathcal{L}_m(Y)|\le P_m\le |V|\,|\mathcal{L}_m(Y)|.
\end{align*}
[guided]
The point of this step is to show that labelled word growth and graph path growth differ only by a bounded multiplicative factor. Define
\begin{align*}
\Lambda_m:\mathcal{P}_m\to\mathcal{A}^m
\end{align*}
by
\begin{align*}
\Lambda_m(e_1,\dots,e_m):=\ell(e_1)\cdots \ell(e_m)
\end{align*}
to be the map that forgets the vertices and remembers only the emitted labels.
First, essentiality identifies the image of this map with the language of the shift. If $p=(e_1,\dots,e_m)\in\mathcal{P}_m$, let $u$ be the initial vertex of $e_1$ and let $v$ be the terminal vertex of $e_m$. Essentiality says that $u$ lies on some bi-infinite path, so the part of that path ending at $u$ supplies a left-infinite path ending at $u$. It also says that $v$ lies on some bi-infinite path, so the part of that path beginning at $v$ supplies a right-infinite path beginning at $v$. Concatenating the left-infinite path, the finite path $p$, and the right-infinite path gives a bi-infinite path containing $p$. Therefore $\Lambda_m(p)$ appears as a length-$m$ block in some point of $Y$, so $\Lambda_m(p)\in\mathcal{L}_m(Y)$. This proves
\begin{align*}
\Lambda_m(\mathcal{P}_m)\subseteq \mathcal{L}_m(Y).
\end{align*}
The reverse inclusion follows from the definition of the presented shift: if $w\in\mathcal{L}_m(Y)$, then $w$ appears in a bi-infinite label sequence read along a bi-infinite graph path, and the corresponding $m$ consecutive edges form a path $p\in\mathcal{P}_m$ with $\Lambda_m(p)=w$. Hence
\begin{align*}
\mathcal{L}_m(Y)\subseteq \Lambda_m(\mathcal{P}_m).
\end{align*}
Thus
\begin{align*}
\mathcal{L}_m(Y)=\Lambda_m(\mathcal{P}_m).
\end{align*}
Now we use right-resolvingness. Fix a word $w=a_1\cdots a_m\in\mathcal{L}_m(Y)$ and a starting vertex $v\in V$. Because the graph is right-resolving, there is at most one outgoing edge from $v$ labelled $a_1$. If that edge exists, its terminal vertex is then fixed. From that terminal vertex, there is at most one outgoing edge labelled $a_2$, and continuing inductively, there is at most one length-$m$ path starting at $v$ and labelled by $w$. Since there are exactly $|V|$ possible starting vertices, the fibre $\Lambda_m^{-1}(\{w\})$ has cardinality at most $|V|$.
Therefore the total number of paths is bounded by summing these fibre bounds over all words:
\begin{align*}
P_m=|\mathcal{P}_m|\le \sum_{w\in\mathcal{L}_m(Y)} |V|=|V|\,|\mathcal{L}_m(Y)|.
\end{align*}
The opposite inequality follows because $\Lambda_m$ maps $\mathcal{P}_m$ onto $\mathcal{L}_m(Y)$, so the number of words cannot exceed the number of paths:
\begin{align*}
|\mathcal{L}_m(Y)|\le P_m.
\end{align*}
Combining the two estimates gives
\begin{align*}
|\mathcal{L}_m(Y)|\le P_m\le |V|\,|\mathcal{L}_m(Y)|.
\end{align*}
[/guided]
[/step]
[step:Pass from bounded multiplicative comparison to equal exponential growth]
Taking logarithms in
\begin{align*}
|\mathcal{L}_m(Y)|\le P_m\le |V|\,|\mathcal{L}_m(Y)|
\end{align*}
gives
\begin{align*}
\frac{1}{m}\log |\mathcal{L}_m(Y)|\le \frac{1}{m}\log P_m\le \frac{1}{m}\log |\mathcal{L}_m(Y)|+\frac{1}{m}\log |V|.
\end{align*}
Since $V$ is finite,
\begin{align*}
\lim_{m\to\infty}\frac{1}{m}\log |V|=0.
\end{align*}
By the [squeeze theorem](/theorems/627),
\begin{align*}
h_{\mathrm{top}}(\sigma|_Y)=\lim_{m\to\infty}\frac{1}{m}\log P_m.
\end{align*}
[/step]
[step:Identify path growth with the spectral radius of the adjacency matrix]
We use the finite non-negative matrix growth formula: if $M$ is a finite non-negative matrix and $\mathbf 1^\top M^m\mathbf 1$ is not eventually zero, then
\begin{align*}
\lim_{m\to\infty}\frac{1}{m}\log \left(\mathbf{1}^{\top}M^m\mathbf{1}\right)=\log \rho(M).
\end{align*}
This is the standard Perron--Frobenius spectral-radius growth formula applied to the total path-counting functional. The hypotheses are satisfied because $M$ is a finite square matrix with non-negative integer entries, and essentiality together with $Y\neq\varnothing$ ensures that the path-counting sequence is not eventually zero. Since $P_m=\mathbf{1}^{\top}M^m\mathbf{1}$, we obtain
\begin{align*}
\lim_{m\to\infty}\frac{1}{m}\log P_m=\log \rho(M).
\end{align*}
Combining this with the previous step yields
\begin{align*}
h_{\mathrm{top}}(\sigma|_Y)=\log \rho(M).
\end{align*}
[/step]
[step:Reduce the nonessential case to the essential part]
Suppose now that $\mathcal{G}$ is not essential. Let $\mathcal{G}_{\mathrm{ess}}$ be the subgraph consisting exactly of the vertices and edges that occur in some bi-infinite path whose label sequence belongs to $Y$. Removing all other vertices and edges does not change the set of bi-infinite labelled paths, and therefore does not change the presented shift $Y$ or its language $\mathcal{L}_m(Y)$ for any $m\in\mathbb{N}$.
The graph $\mathcal{G}_{\mathrm{ess}}$ is essential by construction and remains right-resolving because it is a subgraph of the right-resolving graph $\mathcal{G}$. Applying the essential case to $\mathcal{G}_{\mathrm{ess}}$ and its adjacency matrix $M_{\mathrm{ess}}$ gives
\begin{align*}
h_{\mathrm{top}}(\sigma|_Y)=\log \rho(M_{\mathrm{ess}}).
\end{align*}
This proves both assertions.
[/step]
