Relationship between free probability and deterministic graphs?

I believe the relation between deterministic graphs and free probability you mentioned is not something generic. In fact, the main property of your matrix $M$ which makes connection with free probability (at the best of my knowledge) is not to be the adjacency matrix of some graph, but a Jacobi matrix related to some orthogonal polynomials, which themselves come from random matrix models.

Let me try to develop : We first need some computations.

We have to assume $N$ even to make things properly. The Chebyshev (monic) polynomials $(T_k)_{k\geq0}$ of the first kind satisfy $T_k(x)=x^k+\ldots$ and are orthogonal for the weight $$ w(x)=\frac{1}{\sqrt{1-x^2}}, $$ defined on $[-1,1]$, namey for any $k\neq l$ $$ \int_{-1}^1T_k(x)T_{l}(x)w(x)=0. $$ Their Jacobi matrix (associated with its recurrent coefficients) is actually $M/2$. For our purpose its enough to know that the zeros of $T_N$ are actually the eigenvalues of $M/2$. Moreover, a formula due to Heine yields $$ T_N(x)=\int_{-1}^1\ldots\int_{-1}^1\prod_{i=1}^N(x-x_i)\prod_{1\leq i < j \leq N}|x_i-x_j|^2\prod_{i=1}^Nw(x_i)dx_i. $$ The change of variables $x_i=\cos\theta_i$ gives $$ T_N(x)=\int_{0}^{2\pi}\ldots \int_0^{2\pi}\prod_{i=1}^N(x-\cos\theta_i)\prod_{1\leq i < j \leq N}|\cos\theta_i - \cos\theta_j|^2\prod_{i=1}^Nd\theta_i $$ and by Weyl formula $$ T_N(x)=\int_{\mathcal{U}_N}\det(xI_N-\frac{U+U^*}{2}) dU = \mathbb{E}_{Haar}\Big(\det(xI_N-\frac{U+U^*}{2})\Big) $$ where $dU$ stands for the Haar measure of the unitary group $\mathcal{U}_N$.

Conclusion : The random matrix $U+U^*$, with $U$ distributed according to Haar, has for mean eigenvalues the zeros of $T_N(x/2)$, and equivalently the eigenvalues of $M$. Thus they should have the same limiting distribution as $N\rightarrow\infty$ as soon as that the limiting distribution of $U+U^*$ is deterministic.

One one hand, the limiting distribution of $M$ is indeed known to be the arcsine distribution (note it is also the limiting distribution of the zeros of $T_N$ as $N\rightarrow\infty$, which is known to minimize the logarithmic energy $$ \iint \log\frac{1}{|x-y|}d\mu(x)d\mu(y) $$ over all probability measure $\mu$ on $[-1,1]$, a classical statement in potential theory).

On an other hand, by the invariance property of the Haar measure, the distribution of $U+U^* $ is the same than $A+VAV^*$, with $V$ also distributed according to Haar, which is known to converge by Voiculescu Theorem towards $\mu_A\boxplus\mu_A$, where $\mu_A$ is the limiting distribution of your matrix $A$, namely $\mu_A=\frac{1}{2}(\delta_1+\delta_{-1})$.

I'd like to add that in general, your matrix is a special case of symmetric tridiagonal matrices of the form

$$ \begin{bmatrix} a & b & \cdots & \cdots & 0\\\\ b & a & b & \cdots & 0\\\\ & \ddots & \ddots & \ddots\\\\ 0 & \cdots & &a & b\\\\ 0 & \cdots & &b & a \end{bmatrix} $$

The eigenvalues of this matrix are $$ \lambda_k = a + 2b\cos(k\pi/(n+1)),\qquad 1 \le k \le n. $$

The eigenvectors have a similar nice closed form.

$$ v_{ik} = \sin\left(\frac{ik\pi}{n+1}\right),\qquad 1\le i,k \le n. $$

These facts can probably be quickly derived by looking at the characteristic polynomial.

The relation between free probability and graphs you are looking for comes from the free product of (rooted) graphs, see for example the paper of Accardi, Lenczewski and Salapata https://arxiv.org/abs/math/0609329, where a decompostion of this prodcut as a sum of free operators is given in terms of the individual adjacency operators of the factors.

Now, there are actually two small differences between the free product of K2 (corresponding to $1/2\delta_{-1}+1/2\delta_1$) with itself and the graphs you are considering: First, the free product is actually infinite: $$⋯∘-∘-∘-∘-∘-∘-⋯$$ and second, one needs to consider the vector state $<A~\delta(e),\delta(e)>$, where $e$ is root of the graph, instead of the normalized trace $tr$. However, both differences "vanish" in the limit since almost all the vertexes look locally as belonging to the actual free product.