By Definition 1.1.24, \(G\) is regular of degree \(\mathfrak {d}\) if and only if for all \(x \in V(G)\), \(\deg (x)=\mathfrak {d}\). By Lemma 1.3.3, this is equivalent to having, for all \(x \in V(G)\), \(a \mathbf{1}(x) = \mathfrak {d}\), which is equivalent to \(a \mathbf{1}= \mathfrak {d}\mathbf{1}\) by Definition 1.2.2.

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

Since \(G\) is regular of degree \(\mathfrak {d}\), by Theorem 1.3.4, \(\| a \| \leq \mathfrak {d}\). By Lemma 2.1.2, \(\mathfrak {d}\) is an eigenvalue of \(a\) and hence \(\| a\| \geq \mathfrak {d}\), which is enough to conclude.

We treat differently the case \(\mathfrak {d}=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 \(\mathfrak {d}\neq 0\).

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

In particular

Note that this sum contains \(\mathfrak {d}\) 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 \(\mathfrak {d}\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 1.2.17, 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 \(- \mathfrak {d}\) is an eigenvalue of \(a\). Then by definition there exists a non-zero function \(f \in \ell ^2(G)\) such that \(af=-\mathfrak {d}f\). In particular \(\| af\| =\mathfrak {d}\| f\| \). By the equality case in Lemma 1.3.6, 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 \(\mathfrak {d}\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 2.1.6 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) = \mathfrak {d}\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 \(\mathfrak {d}\geq 1\). Hence we can apply Lemma 2.1.6 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=- \mathfrak {d}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 \(-\mathfrak {d}\) is an eigenvalue of \(a\).

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

The operator \(a|_{\mathbf{1}^\perp }\) is a self-adjoint operator in finite dimension by Lemma 2.2.1, 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 2.2.2, there exists a function \(f : V(G) \rightarrow \mathbb {C}\) and a real number \(\lambda \) such that \(af=\lambda f\), \(|\lambda |=\mathfrak {d}\) and \(\sum _{x \in V(G)} f(x)=0\). Since \(\lambda \in \mathbb {R}\), either \(\lambda = \mathfrak {d}\) or \(\lambda =-\mathfrak {d}\).

• If \(\lambda = \mathfrak {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 \(\mathfrak {d}\) for \(a\) is at least \(2\). By Proposition 2.1.4, the number of connected components of \(G\) is \(\geq 2\) and hence \(G\) is disconnected.

• If \(\lambda = -\mathfrak {d}\), then \(-\mathfrak {d}\) is an eigenvalue of \(a\). By Proposition 2.1.5, \(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 2.2.3,

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

Hence

which goes to \(0\) as \(N \rightarrow \infty \) by Theorem 2.2.7. So \(\lim _N \mathrm{Prob}_{N,\mathfrak {d}}^{G}(A) = 0\) and \(\lim _N \mathrm{Prob}_{N,\mathfrak {d}}^{G}(B)=0\) which allows to conclude.