By Definition 44, \(G\) is regular of degree \(\delta \) if and only if for all \(x \in V(G)\), \(\deg (x)=\delta \). By Lemma 84, this is equivalent to having, for all \(x \in V(G)\), \(a \mathbf{1}(x) = \delta \), which is equivalent to \(a \mathbf{1}= \delta \mathbf{1}\) by Definition 65.

Since \(G\) is finite, \(\mathbf{1}\in \ell ^2(G)\) by Lemma 68. Furthermore, \(\mathbf{1}\neq 0\) by Lemma 66. By Lemma 109, if \(G\) is regular of degree \(\delta \), then \(a \mathbf{1}= \delta \mathbf{1}\). We conclude by the definition of eigenvalue and eigenvector.

Since \(G\) is regular of degree \(\delta \), by Theorem 85, \(\| a \| \leq \delta \). By Lemma 110, \(\delta \) is an eigenvalue of \(a\) and hence \(\| a\| \geq \delta \), which is enough to conclude.

We treat differently the case \(\delta =0\), where \(a\) is identically equal to \(0\) and every function \(V(G) \rightarrow \mathbb {C}\) is in the kernel of \(a\), and hence the result holds since the connected components of \(G\) are all the \(\{ x\} \) for \(x \in V(G)\). Now assume \(\delta \neq 0\).

Lemma 83 implies that all locally constant functions are included in the eigenspace associated to the eigenvalue \(\delta \). Let us show the other inclusion. Assume \(f\) is such that \(af=\delta f\). In particular, \(\| af\| =\delta \| f\| \) and hence by the equality case in Lemma 87,

In particular

Note that this sum contains \(\delta \) terms and, for all \(d,d' \in \mathrm{dartSet}(x)\), \(f(\mathrm{end}(d))=f(\mathrm{end}(d'))\) so all of its terms are equal. Since \(\delta \neq 0\), we obtain that, for all \(d, d' \in \mathrm{dartSet}(G)\), \(f(\mathrm{end}(d))=f(\mathrm{end}(d'))\), i.e. \(f\) is locally constant.

By Theorem 80, the dimension of the space of locally constant functions is exactly the number of connected components of \(G\), which allows to conclude.

Assume \(G\) is bipartite. Then there exists a partition \(U_1, U_2\) of \(V(G)\) such that any edge of \(G\) has one end in \(U_1\) and the other in \(U_2\). Take \(f = \mathbf{1}_{U_1}-\mathbf{1}_{U_2}\). The function \(f\) is not equal to \(0\), since \(U_1\) is not empty, and for \(x \in U_1\), \(f(x)=1 \neq 0\). For any \(x, y \in V(G)\) adjacent, one of the following occurs:

• either \(x \in U_1\) and \(y \in U_2\), and hence \(f(x)=1=-f(y)\);

• or \(x \in U_2\) and \(y \in U_1\), and hence \(f(x)=-1=-f(y)\).

Now assume there exists a non-zero function \(f : V(G) \rightarrow \mathbb {C}\) such that, for any \(x, y \in V(G)\) adjacent, \(f(x)=-f(y)\). By assumption, \(E(G)\) is not empty, so there exists \(x \in V(G)\) with at least an adjacent vertex. For any \(y \in V(G)\), since \(G\) is preconnected, there exists a walk \(w\) from \(x\) to \(y\). We check by induction that the hypothesis on \(f\) implies \(f(y) = (-1)^{\mathrm{length}(w)}f(x)\). Since \(f \neq 0\), there exists \(y \in V(G)\) such that \(f(y) \neq 0\), from which we deduce \(f(x) \neq 0\). We define \(U_1=\{ y \in V(G) : f(y)=f(x)\} \) and \(U_2=\{ y \in V(G) : f(y)=-f(x)\} \).

• By the previous computation, \(V(G) = U_1 \cup U_2\).

• Since \(f(x) \neq 0\), \(U_1 \cap U_2 = \emptyset \).

• \(U_1\) contains \(x\) and is hence not empty. We picked \(x\) so that it has at least one adjacent edge, which will be an element of \(U_2\), and hence \(U_2\) is not empty.

• For any edge \(e \in E(G)\) linking two vertices \(y, z\), we check that \(y \in U_1 \Rightarrow x \in U_2\) and \(y \in U_2 \Rightarrow z \in U_1\) thanks to the fact that \(f(y)=-f(z)\).

So, \(G\) is bipartite.

Let us assume that \(- \delta \) is an eigenvalue of \(a\). Then by definition there exists a non-zero function \(f \in \ell ^2(G)\) such that \(af=-\delta f\). In particular \(\| af\| =\delta \| f\| \). By the equality case in Lemma 87, for any \(x \in V(G)\), any \(y, z\) adjacent to \(x\), \(f(y)=f(z)\). But then we have for \(x \in V(G)\)

a sum with \(\delta \neq 0\) terms in which all terms are equal. Hence for any \(y\) adjacent to \(x\), \(f(y)=-f(x)\). Since \(f \neq 0\), there exists \(x \in V(G)\) such that \(f(x) \neq 0\). We apply Lemma 114 to the graph \(\mathrm{cc}(x)\) with the restriction of the function \(f\) (which we can do as \(\mathrm{cc}(x)\) is preconnected and has at least one edge since \(\deg (x) = \delta \geq 1\)), and obtain that \(\mathrm{cc}(x)\) is bipartite.

Now, let us assume that one connected component \(C\) of \(G\) is bipartite. \(C\) is not empty so it contains at least one vertex, which has at least one incident edge as the graph is regular of degree \(\delta \geq 1\). Hence we can apply Lemma 114 to \(C\) and obtain a function \(f\) such that, for any \(x\), \(y\) adjacent, \(f(x)=-f(y)\). Then, let us define \(F(x) = f(x)\) if \(x \in C\) and \(0\) otherwise. \(F \in \ell ^2(G)\) since \(G\) is finite. We check that \(aF=- \delta F\) (here using the fact that, if \(x\), \(y\) are adjacent, then \(x \in C \Leftrightarrow y \in C\)). \(F \neq 0\) as there exists \(x \in C \subset V(G)\) for which \(F(x) = f(x) \neq 0\). So \(-\delta \) is an eigenvalue of \(a\).

This is classic theory of self-adjoint bounded operators, as \(\mathbf{1}\) is an eigenvector of \(a\) by Lemma 110.

The operator \(a|_{\mathbf{1}^\perp }\) is a self-adjoint operator in finite dimension by Lemma 115, and hence its spectrum is entirely made of real eigenvalues and its norm is the supremum of their absolute values. Hence there exists a function \(f \in \mathbf{1}^\perp \) and \(\lambda \in \mathbb {R}\) such that \(a|_{\mathbf{1}^\perp }f = \lambda f\), \(f \neq 0\) and \(|\lambda |=\| a|_{\mathbf{1}^\perp }\| \). The function \(f\) and the number \(\lambda \) satisfy the claim.

By Lemma 116, there exists a function \(f : V(G) \rightarrow \mathbb {C}\) and a real number \(\lambda \) such that \(af=\lambda f\), \(|\lambda |=d\) and \(\sum _{x \in V(G)} f(x)=0\). Since \(\lambda \in \mathbb {R}\), either \(\lambda = d\) or \(\lambda =-d\).

• If \(\lambda = d\), then since \(f\) is not constant (otherwise it would be equal to \(0\) as \(\sum _{x \in V(G)}f(x)=0\)), the multiplicity of the eigenvalue \(d\) for \(a\) is at least \(2\). By Proposition 112, the number of connected components of \(G\) is \(\geq 2\) and hence \(G\) is disconnected.

• If \(\lambda = -d\), then \(-d\) is an eigenvalue of \(a\). By Proposition 113, \(G\) has a connected component \(C\) that is bipartite.

  • If \(C=V(G)\) then \(G\) is bipartite.

  • Otherwise \(G\) is disconnected as it has a strict connected component.

Denote \(A = "G_{\vec{\pi }} \text{ is disconnected}"\) and \(B = "G_{\vec{\pi }} \text{ is bipartite}"\). By Proposition 117,

We check directly that \(2 \sqrt{2 \delta - 1} {\lt} \delta \). Hence taking \(\epsilon = (\delta - 2 \sqrt{2 \delta - 1})/2 {\gt} 0\) we obtain

Hence

which goes to \(0\) as \(n \rightarrow \infty \) by Theorem 121. So \(\lim _n \mathrm{Prob}_{n,\delta }(A) = 0\) and \(\lim _n \mathrm{Prob}_{n,\delta }(B)=0\) which allows to conclude.

For \(w \in V(\mathbb {T}_\delta )\), we have \(\mathrm{dartSet}(w) = \{ (w,i), i \in [\delta ]\} \) which has cardinal \(\delta \).

By induction.

• If \(m=0\) (the walk is empty) then \(w'=w = \pi (w)\) since \(w\) is reduced.

• Otherwise, the walk is the concatenation of \(d_1\) and the rest of the walk. Then by the induction hypothesis \(w' = \pi (\mathrm{end}(d_1) i_2 \ldots i_m)\). The conclusion follows from \(\mathrm{end}(d_1) = \pi (wi_1)\) by Definition 123 together with the properties of \(\pi \).

Let \((d_k)_{1 \leq k \leq m}\) be a dartwalk from \(w\) to \(w'\) and denote \(w'' = \Pi _\delta ^{\mathrm{dw}}(d_k)_{1 \leq k \leq m}\). By Lemma 126, \(w' = \pi (w w'')\) so the range of the image is included in the claimed set.

Let us prove it is a bijection by exhibiting an inverse. We define a function \(\Psi \) which to a word \(w''=i_1 \ldots i_m\) in \(W_\delta \) such that \(w'=\pi (ww'')\) associates the darts \((d_k)_{1 \leq k \leq m}\) where \(d_k = (\pi (w i_1 \ldots i_{k-1}), i_k)\). This is a dartwalk since \(\mathrm{end}(d_k) = \pi (\pi (w i_1 \ldots i_{k-1})i_{k}) = \pi (w i_1 \ldots i_k) = \mathrm{start}(d_{k+1})\) by the properties of \(\pi \). Also \(\mathrm{start}(d_1)= \pi (w) = w\) and \(\mathrm{end}(d_m) = \pi (w w'') = w'\). So \(\Psi (w'')\) is a dartwalk from \(w\) to \(w'\).

Now we check that \(\Psi \) is an inverse of \(\Pi _\delta ^{\mathrm{dw}}\) directly from the definition.

Let \(p = (d_i)_{1 \leq k \leq m}\) be a dartwalk and denote \(w = i_1 \ldots i_m\) its image by \(\Pi _\delta ^{\mathrm{dw}}\) and \((x_i)_{0 \leq i \leq m}\) its support.

• Assume \(w\) is not reduced. Then there exists \(1 \leq k {\lt} m\) such that \(i_k=i_{k+1}\). Then we check \(x_{k-1}=x_{k+1}\) and hence the walk is not a path.

• Assume \(w\) is reduced. Let \(1 \leq k \leq l \leq m\). Assume \(x_k=x_l\). Then the dartwalk \((d_i)_{k {\lt} i \leq l}\) is a closed dartwalk. By Lemma 129, \(\pi (i_{k+1} \ldots i_l)\) is the empty word. Since \(w\) is reduced, it contains no non-trivial words that reduce to the empty word, and hence we have \(k=l\).

Let \(w\), \(w'\) be two vertices of \(\mathbb {T}_\delta \), i.e. two elements of \(V_\delta \). We need to prove that there is a unique path from \(w\) to \(w'\). By Lemma 128, any walk from \(w\) to \(w'\) is given by a unique word \(w''\) such that \(w'=\pi (w w'')\). By Lemma 130, the walk is a path iff the word \(w''\) is reduced. Note that the word \(w''=\pi (w^{-1}w')\) is always reduced, satisfies \(w'=\pi (w w'')\), and hence induces a path from \(w\) to \(w'\). For any path, since \(w''\) is reduced, \(w''=\pi (w'') = \pi (w^{-1}ww'') = \pi (w^{-1}w')\) by properties of \(\pi \). So this is the unique path from \(w\) to \(w'\).

Take \(f \in \ell ^2(G)\). By Lemma 89,

so by the triangular inequality

[todo:continue]