Proof. We first record the consequences of minimality, with contour incidences understood throughout.

Face words and mergers. A bounded-face word cannot be freely trivial. Indeed, the diagram identity expresses the exterior word as a product of conjugates of the face words, each used once. Omitting a freely trivial factor and applying van Kampen’s lemma again gives a diagram with fewer faces for the same exterior word. Its prescribed exterior paths lift identically by determinism of \(X\). A closed walk in \(P\) shorter than \(\sigma(P)\) cancels to the empty walk, so every face has the claimed lower perimeter bound.

Suppose two distinct bounded faces with the same copy assignment share an edge. That edge is not a bridge. Delete it and join the two contours along its former incidences. Every remaining step lies in the same copy, so the merged contour is an admissible closed walk there. Exactly one bounded face disappears. Other contacts between the old contours may produce repeated vertices or bridges, which our diagram category allows. Thus this configuration contradicts minimality of \(F\).

The same operation excludes an edge shared by a bounded face and an adjustable exterior side with the same assignment. Replace this particular occurrence of the edge in the side by the rest of the bounded contour. The resulting side is still a walk in that copy with the same endpoints. Its prescribed position among the exterior sides is unchanged, and again one bounded face disappears.

Leaves and bounded-face bridges. There is no unmarked vertex of valence one. Its leaf edge gives an immediate backtrack; on the exterior this lies within one adjustable side, because a side break would be marked and a generator side has marked endpoints. Erasing the leaf preserves the assignments and lowers the edge count.

There is also no bridge whose two incidences belong to a bounded face. After its open edge is removed, the exterior contour lies wholly in one component. Keep that component and discard the other component together with the bridge. On the affected bounded contour this replaces \(q e\gamma e^{-1}q'\) by \(q q'\), where \(e\) is the bridge and \(\gamma\) is the entire excursion around the discarded component. The retained walk is still closed and still lies in the assigned copy; no free triviality of \(\gamma\) is required. The exterior, including its side data, is unchanged. The face count cannot increase—also directly from \(F=E-V+1\)—and the edge count decreases.

Short arcs. The incidence type on either side of a compressed arc is constant: it is a bounded face or an exterior side of the prescribed decomposition. Changes of exterior side occur at marked vertices and are not suppressed. An arc with a generator-side incidence therefore has length one. By the preceding restrictions, an arc incident to a bounded face has either such an incidence on the other side or a different copy assignment there.

Consider an arc with different assignments and length greater than two. Its word is freely reduced. Otherwise a consecutive cancelling pair has an unmarked bivalent midpoint and two distinct endpoints in the diagram. The latter assertion holds even for a loop arc: its internal vertices are distinct and closure occurs only at the two ends of the entire arc. Contract the cancelling pair as a length-two tree, identifying its outer endpoints, which have the same group value. At each incident contour the two steps cancel, so assignments and side data are preserved. This non-loop contraction preserves \(F\) and lowers the edge count, a contradiction.

If the arc had length at least \(\lambda\sigma(Q)\) for one assignment \(Q\), its first \(\lceil\lambda\sigma(Q)\rceil\) edges would be a nonbacktracking path shorter than the girth. It is simple in \(Q\), hence also in the other source by the vertex embeddings. This contradicts Lemma 3. Arcs of length at most two are already shorter than the threshold. This proves (a) and (b).

Counting. There is a marked vertex, so suppression cannot leave an exceptional unmarked circle component. Every unmarked surviving vertex has valence at least three. If \(v_D\) is the compressed vertex count, then \[v_D-b+F=1,\qquad 2b\ge3(v_D-m), \qquad b\le3F+3m-3.\] By (a), every bounded face has at least \(1/\lambda\) arc incidences, counted with multiplicity. Their total is at most \(2b\), so \[F/\lambda\le2b\le6F+6m-6.\] This is the first inequality in (2). Since \(\lambda\le1/12\), it gives \(F\le m-1\) and then \(b\le6m\). The same formulas cover trees and the isolated marked vertex. ◻

Proof of Proposition 5. Avoidance. For (3), close the given avoiding path by one designated side through \(c_P\). Then \(m\le L+1\), and no other side has center \(c_P\). Use a minimal diagram. An arc incidence on the designated side is opposite a bounded face of different assignment or an exterior incidence across a bridge. In the latter case the other incidence cannot also lie in the designated side. If it did, the interval from that bridge’s first traversal to its retraversal in the linear side walk would contain no prescribed side break. Excise the visited component and the bridge. This shortens only the designated side, preserving its endpoints and copy assignment, and cannot increase \(F\). It contradicts minimality. This argument concerns marked positions; additional visits to a marked vertex do not insert a side break.

Thus every designated-side incidence has length less than \(\lambda\sigma(P)\), either by Lemma 4(b) or because its opposite incidence is a generator side. There are at most \(2b\) such occurrences. The adjusted walk inside \(P\) has length at most \(12(L+1)\lambda\sigma(P)\), giving the distance bound. Empty walks, including the case \(x=a\), satisfy it as well.

Simplicity of the Cayley graph. For part [item:simple-cayley], consider a closed word of one or two generator sides. Strict \(\lambda<1/12\) in (2) forces \(F=0\). The exterior contour of a tree is freely trivial. This excludes identity generators, unintended coincidences of generator edges, and generator involutions, as claimed.

Short fillings. To establish uniform thinness, we first show that every edge loop of length \(n>0\) in \(\widehat X\) has a filling with at most \(12n\) relation faces of perimeter at most four. For its \(m\le n\) sides, take the compressed minimal diagram. Choose one standard path for each arc, consistently under reversal. Keep the unit edge if the arc has a generator-side incidence. Otherwise an assignment at an incidence contains both endpoints, so use the two-edge path through that copy’s center.

Around a bounded face assigned to \(P\), replace each standard path by the two-edge path through \(c_P\). Each replacement uses one closed walk of length at most four. The resulting contour freely contracts through that one center. Thus the standard exterior walk can be filled at cost at most the number of bounded-face incidences. On an exterior adjustable side, make the same replacements through its prescribed center. The consecutive pairs reduce to the required single cone passage. If an inflated side was empty, insert its desired backtrack freely. Generator sides need no change. The total cost is at most the number of bounded-face and exterior adjustable-side incidences, hence at most \(2b\le12m\le12n\).

This filling argument works for the singular diagrams being used. More explicitly, for directed edge paths with their endpoint values, the plane-diagram identity expresses the exterior contour as a product of conjugates of the bounded contours, one for each face, up to free edge cancellations and their inverses. Substituting the indicated fillings gives the claimed product of short relations. Conversely, the van Kampen construction from this product gives a plane diagram over the graph: inverse-edge folds identify only vertices with the same target value.

From fillings to thin triangles. The bound implies the coarse filling hypothesis in (Bridson and Haefliger 1999, III.H.2.1 and III.H.2.9) with universal constants. Subdivide a rectifiable loop of length \(\ell\) into \(O(\ell+1)\) arcs of length at most one. Choose nearby vertices at distance at most one and join successive ones by paths of at most three edges. Fill this edge loop as above. In a resulting small-face diagram with \(f\) faces and exterior length \(n\), \[2E=n+\sum_F|\partial F|\le n+4f,\qquad V\le E+1.\] Thicken its finite plane graph to a regular neighborhood, using vertex disks and edge strips, and cap the bounded contour components. The result is a disk. The vertex regions are mapped to vertices, the strips along their edges, and each cap has a boundary of bounded image perimeter. Triangulation has total cost \(O(E+V+f)\); each triangle can be assigned a map of uniformly bounded image diameter. Coarse fillings do not require continuous maps on their interiors. An additional collar with \(O(n)\) triangles restores the prescribed exterior parameterization: each block joins a unit-edge traversal to that traversal with its inserted vertex pauses, and its image lies in the same edge. The short paths to the original subdivision points give an annulus with \(O(\ell+1)\) further triangles of bounded image diameter. Constant loops or empty approximating walks are filled separately by a bounded number of triangles.

The constants in this construction are independent of the graphs, alphabet, and \(\lambda\). A connected unit-edge graph is geodesic, regardless of local finiteness. The cited theorem therefore gives a hyperbolicity constant depending only on these universal coarse filling constants. Enlarging it to an integer accounts for moving points on triangle sides to vertices and gives the required \(D_0\). ◻

Proof. Take such a \(Q\) and a shared vertex \(x\), and write \(B=c_Q\). The path \(A,x,B\) is a length-two geodesic. A geodesic from \(B\) to \(R\) avoids \(A\), since passing through \(A\) would give length \(2+d(A,R)>d(A,R)\). All distances in the rest of this paragraph are in \(\widehat X\).

If \(d(A,R)\ge t\), let \(z\) be the vertex at distance \(t\) along the chosen \(A\)-to-\(R\) geodesic. Its distance from every vertex of \(A,x,B\) is at least \(t-2>D_0\). Thinness supplies a vertex \(y\) on the \(B\)-to-\(R\) side with \(d(y,z)\le D_0\). A shortest bridge between them avoids \(A\), because \(d(A,z)=t>D_0\). Follow \(x,B,y,z,a\), using that bridge and the indicated geodesic segments. This walk avoids \(A\), and its length is at most \[1+(2+t+D_0)+D_0+(t-1)=L_0.\] If \(d(A,R)<t\), use instead the walk from \(x\) through \(B\) to \(R\) and back to \(a\). It avoids \(A\) and has length at most \(1+d(B,R)+d(A,R)-1\le2d(A,R)\le L_0\).

Apply (3) to obtain \(d_P(x,a)\le12(L_0+1)\lambda\sigma(P)\). Intrinsic vertex distances are integers, so taking the floor gives the claimed radius. Crucially, the chosen \(a\) does not depend on \(Q\) or \(x\). ◻

Proof. Every finite cycle is a sum of closed walks. The label of any such walk is trivial in \(\Gamma\), so a finite van Kampen diagram over the presentation expresses its edge chain, modulo two, as the sum of the chains of its bounded-face walks. Each lies in a copy. This proves spanning.

Suppose finitely many nonzero cycles in distinct copies sum to zero. Choose a group-vertex root \(R\) and a participating copy \(P\) whose center is farthest from \(R\). By Lemma 6, all its intersections with the other participating copies lie in one ball \(B_P\), which is an induced tree by (9). Every nonzero edge coefficient in its cycle must cancel against an edge of another participating copy. Both endpoints therefore lie in \(B_P\), and inducedness puts the edge itself in that tree. A tree has no nonzero finite cycle, a contradiction. ◻

Proof. Write \(n=n_i\), \(k=k_i\), and \(w=w_i\), and choose \(C\) uniformly among the \(k\)-dimensional subspaces containing \(\langle w\rangle\). For a fixed \(z\notin\langle w\rangle\), the quotient by \(\langle w\rangle\) gives \[ \Pr(z\in C) =\frac{p^{k-1}-1}{p^{n-1}-1} <p^{k-n}. \tag{11}\] Indeed, a uniform \(a\)-dimensional subspace of an \(N\)-dimensional vector space contains a fixed nonzero vector with probability \((p^a-1)/(p^N-1)\), by counting nonzero vectors and symmetry. Nonzero vectors of \(\langle w\rangle\) have full support.

Orthogonal complementation is a bijection from the sample space just used to the \((n-k)\)-dimensional subspaces of the \((n-1)\)-dimensional space \(w^\perp\). Consequently, for a fixed nonzero \(z\), \[ \Pr(z\in C^\perp)= \begin{cases} \displaystyle\frac{p^{n-k}-1}{p^{n-1}-1}<p^{1-k}, &z\in w^\perp,\\[6pt] 0,&z\notin w^\perp. \end{cases} \tag{12}\] This argument uses nondegeneracy of the form on the ambient coordinate space, not of its restriction to \(w^\perp\); it remains valid when \(\langle w,w\rangle=0\).

We bound the number of low-weight vectors. Put \(r=\lfloor\eta n\rfloor\) and \(q=\eta/(1-\eta)<1\). The binomial theorem gives \[q^r\sum_{j=0}^r\binom nj \le \sum_{j=0}^r\binom nj q^j \le (1+q)^n.\] It follows that \[\sum_{j=0}^r\binom nj \le q^{-\eta n}(1+q)^n =2^{H_2(\eta)n}, \qquad H_2(t)=-t\log_2t-(1-t)\log_2(1-t).\] Here \(H_2(1/100)<9/100\): use \(\log_2 100<7\), \(-\log(1-\eta)\le\eta/(1-\eta)\), and \(\log2>1/2\). Since \(p\ge2\), the Hamming ball therefore satisfies \[ \bigl|\{z:|\mathop{\mathrm{supp}}z|\le r\}\bigr| =\sum_{j=0}^r\binom nj(p-1)^j \le p^{\eta n}2^{H_2(\eta)n} \le p^{(\eta+H_2(\eta))n} <p^{n/4}. \tag{13}\] Every nonzero vector in this ball lies outside \(\langle w\rangle\). By (11)–(13) and the union bound, the probability that either \(C\) or \(C^\perp\) contains such a vector is less than \[p^{n/4}\bigl(p^{k-n}+p^{1-k}\bigr) \le p^{-n/4}+p^{3/2-n/4}<1,\] where \(k=\lfloor n/2\rfloor\) and \(n>100\). Thus a suitable \(C\) exists. ◻

Proof. The inclusion from right to left follows from (14). For the converse, let \[z=\sum_{Q\in\mathcal F}z_Q\in W_0\cap\mathbb F_p^P, \qquad 0\ne z_Q\in C_Q^\perp,\] where \(\mathcal F\) is finite and its copies are distinct. Such an expression is obtained by combining terms on the same copy and discarding zero terms.

Suppose that \(\mathcal F\) contains a copy different from \(P\). Root the coned graph at \(R=c_P\), and choose \(Q\in\mathcal F\setminus\{P\}\) whose center is farthest from \(R\). Every other copy in \(\mathcal F\), and also \(P\) itself, has center at distance from \(R\) at most \(d_{\widehat X}(c_Q,R)\). Lemma 6 places all their vertex intersections with \(Q\) in one intrinsic ball \(B_Q\subseteq Q\). If \(Q\) has type \(j\), Proposition 7 gives \[|B_Q|<\eta n_j<|\mathop{\mathrm{supp}}z_Q|.\] Choose \(h\in\mathop{\mathrm{supp}}z_Q\setminus B_Q\). Then \(h\notin P\) and \(h\) belongs to no other copy in \(\mathcal F\). The \(h\)-coordinate of \(z\) is therefore \(z_Q(h)\ne0\), contradicting \(z\in\mathbb F_p^P\). Hence the expression has no term away from \(P\), and \(z\in C_P^\perp\). ◻

Proof. Let \(q_P:\mathbb F_p^P\to V\) be the restriction of the quotient map. Lemma 10 gives \[\ker q_P=C_P^\perp.\] For \(z\in\mathbb F_p^P\) and \(\omega\in\Omega\), \[\omega(q_P(z)) =\sum_{h\in P}z(h)\omega(hv_*) =\langle z,X_\omega|_P\rangle.\] Thus \(X_\omega|_P\) annihilates \(C_P^\perp\), and belongs to \((C_P^\perp)^\perp=C_P\).

Conversely, if \(a\in C_P\), the rule \[q_P(z)\longmapsto\langle z,a\rangle\] is a well-defined linear functional on \(q_P(\mathbb F_p^P)\). Extend a basis of this subspace to a basis of \(V\), and extend the functional linearly to obtain \(\omega\in\Omega\). Then \(X_\omega|_P=a\), proving surjectivity. No continuity condition is lost in this extension, since \(V\) is discrete.

The map \(\operatorname{res}_P\) is a continuous homomorphism of compact groups onto the finite group \(C_P\). Its pushforward of Haar probability is translation-invariant and hence uniform on \(C_P\). As \(|C_P|=p^{k_i}\), formula (16) follows. ◻

Proof. Write \(n=|P|\), and let \(M=\{h\in P:X_\omega(h)\ne w_P(h)\}\). By Lemma 12, the restriction \(X_\omega|_P\) belongs to \(C_P\), and \(w_P\in C_P\) by Lemma 9. Their difference is nonzero, since \(P\) is invalid. The primal-distance bound therefore gives \(|M|>\eta n\).

At a vertex of \(M\), the decoder returns either the empty set or a \(d\)-element set different from the prescribed \(J_P(h)\). In either case at least one prescribed incidence is missing. Consequently, writing \(b=|B|\), we have both \[db-2e_{\omega,P}(B)\ge |M\cap B| \quad\text{and}\quad db-2e_{\omega,P}(B)\ge |\partial_P B|.\] If \(n-b\ge\eta n/2\), then \(\min(b,n-b)\ge(\eta/2)b\). The edge-expansion bound in Proposition 7 yields \[|\partial_P B|\ge\kappa\min(b,n-b) \ge(\eta\kappa/2)b\ge cb.\] Otherwise, \[|M\cap B|\ge |M|-(n-b)>\eta n/2 \ge(\eta/2)b\ge cb.\] Here we used \(c=(\eta/2)\min(\kappa,1)\). The assertion for \(B=\varnothing\) is included. ◻

Proof. The local deficits cannot simply be added over copies, since their vertices and edges can overlap. Instead, we bound the cycle rank \(b_1(A)=\dim Z_1(A;\mathbb F_2)\). Euler’s identity \[|E(A)|=|Y|-\#\pi_0(A)+b_1(A)\] holds also for isolated vertices and the empty graph. It shows that the desired deficit follows from \[b_1(A)\le\bigl(d/2-1-c/4\bigr)|Y|.\] We will obtain this bound by charging the ranks of successive copy coordinates to pairwise disjoint subsets of \(Y\).

Eliminating cycle coordinates. We regard the finite-dimensional space \(\mathcal L=Z_1(A;\mathbb F_2)\) as a subspace of \(Z_1(X;\mathbb F_2)\). Lemma 8 provides the algebraic direct-sum decomposition \[Z_1(X;\mathbb F_2)=\bigoplus_P Z_1(P;\mathbb F_2),\] with coordinate maps \(\operatorname{pr}_P\). These are the coordinates in the algebraic decomposition, not restrictions of edge chains to \(P\): a projected cycle can contain edges absent from the original cycle. Only finitely many coordinates can be nonzero on \(\mathcal L\): choose a finite basis of \(\mathcal L\) and take the union of its finite coordinate supports. Call these copies \(P_1,\ldots,P_N\), ordered by nonincreasing distance of their centers from a fixed group-vertex root \(R\) in \(\widehat X\). Ties may be resolved arbitrarily.

For \(1\le j\le N+1\), set \[\mathcal L_j= \{z\in\mathcal L:\operatorname{pr}_{P_i}z=0\text{ for }i<j\}.\] Then \(\mathcal L_1=\mathcal L\), \(\mathcal L_{N+1}=0\), and rank-nullity gives \[ \dim\mathcal L= \sum_{j=1}^N\dim\operatorname{pr}_{P_j}(\mathcal L_j). \tag{24}\] If \(\mathcal L=0\), this is understood as an empty sum.

Localizing projected cycles. Fix a step \(j\), put \(P=P_j\), and choose the induced intrinsic tree ball \(B_P\) given by Lemma 6 for this root. It contains every vertex of \(P\) shared with any of the other remaining copies \(P_{j+1},\ldots,P_N\). Let \[D_P=B_P\cup(A\cap P),\] where \(A\cap P\) has vertex set \(Y\cap P\) and the edges common to \(A\) and \(P\). We claim that \[ \operatorname{pr}_P(\mathcal L_j)\subseteq Z_1(D_P;\mathbb F_2). \tag{25}\] Indeed, let an edge \(e\) occur with nonzero coefficient in \(\operatorname{pr}_P z\) for \(z\in\mathcal L_j\). If \(e\) does not belong to \(A\), its coefficient must cancel with a coefficient from another remaining copy, because the total chain \(z\) is supported in \(A\). Both endpoints of \(e\) are consequently shared with that copy and lie in \(B_P\). As the ball is induced in \(P\), the edge \(e\) itself lies in \(B_P\). All other edges of \(\operatorname{pr}_P z\) lie in \(A\cap P\). The projection is already a cycle in \(P\), so the claimed inclusion follows. In particular, \[ \dim\operatorname{pr}_P(\mathcal L_j)\le b_1(D_P). \tag{26}\]

Figure 1 summarizes the bookkeeping in the next step. The projected cycle may acquire edges in the overlap tree, but its other edges remain enabled edges on \(Y\). The tree can contribute to a cycle only through multiple attachments of an exterior component.

Bounding exterior cycles and attachments. If \(P\) is valid, \(Y\cap P=\varnothing\), so \(D_P=B_P\) is a tree and the right side is zero. Suppose from now on that \(P\) is invalid, and write \(\sigma=\sigma(P)\) and \(r\) for the radius of \(B_P\). Thus \(r\le\sigma/16\) and \(\sigma>\max(16,20/c)\).

Consider the connected components \(C\) of the graph obtained from \(D_P\) by deleting the vertices of \(B_P\). Their vertex sets partition \((Y\cap P)\setminus B_P\). Let \(l_C\) be the number of edges joining \(C\) to \(B_P\). Since \(B_P\) is a connected tree, the Euler characteristic formula for graph cycle rank gives \[ b_1(D_P)=\sum_C\bigl(b_1(C)+\max(0,l_C-1)\bigr). \tag{27}\] This formula includes components with no attachment: such a component contributes only its own cycle rank.

All edges of \(C\) are enabled copy edges, and all enabled copy edges between its vertices occur in \(C\), by the definition of \(A\). If \(C\) is cyclic, it has at least \(\sigma\) vertices. Applying Lemma 15 to its vertex set and using connectedness, we obtain \[ \begin{split} b_1(C)&=|E(C)|-|C|+1\\ &\le\bigl(d/2-1-c/2+1/\sigma\bigr)|C|. \end{split} \tag{28}\] The same bound holds for an acyclic \(C\), because then \(b_1(C)=0\) and the displayed coefficient is positive. Here \(d\ge3\) and \(0<c\le\eta/2=1/200\).

We next bound the extra rank caused by attachments to the tree. Choose two distinct attachment edges, and denote their endpoints in \(C\) by \(v,v'\) and their endpoints in \(B_P\) by \(b,b'\). A shortest path in \(C\) from \(v\) to \(v'\), these two edges, and the tree path from \(b'\) to \(b\) form a simple cycle in \(P\). This remains true if one pair of endpoints agrees, using the corresponding path of length zero; both pairs cannot agree because \(P\) is simple. The tree path has length at most \(2r\), since both its endpoints lie in the intrinsic ball of radius \(r\). Girth therefore gives \[ \mathop{\mathrm{dist}}_C(v,v')\ge\sigma-2r-2>\sigma/2. \tag{29}\] In particular, all the attachment endpoints in \(C\) are distinct.

If \(l_C\ge2\), the intrinsic balls in \(C\) of radius \(\lfloor\sigma/4\rfloor\) centered at these endpoints are pairwise disjoint, by (29). Each contains at least \(\lfloor\sigma/4\rfloor+1>\sigma/4\) vertices: take an initial segment of a shortest path to any other attachment endpoint. Thus \[ \max(0,l_C-1)\le(4/\sigma)|C|. \tag{30}\] For \(l_C=0\) or \(1\) the same inequality is immediate.

Combining (27), (28), and (30), and using \(5/\sigma<c/4\), yields \[ \begin{split} b_1(D_P) &\le\bigl(d/2-1-c/2+5/\sigma\bigr) |(Y\cap P)\setminus B_P|\\ &\le\bigl(d/2-1-c/4\bigr)|(Y\cap P)\setminus B_P|. \end{split} \tag{31}\] As observed above, this last bound holds also for a valid copy, since both sides then vanish.

Summing over disjoint vertex sets. The exterior sets charged in (31) are pairwise disjoint. Indeed, if \(j<k\), the center of \(P_k\) is no farther from \(R\) than the center of \(P_j\). Lemma 6 therefore implies \[P_j\cap P_k\subseteq B_{P_j}.\] Consequently \((Y\cap P_j)\setminus B_{P_j}\) misses all of \(P_k\), including its charged exterior. The non-strict distance comparison also covers ties in the elimination order.

Summing (26) and (31) in (24) now gives \[\dim Z_1(A;\mathbb F_2)\le\bigl(d/2-1-c/4\bigr)|Y|.\] The coefficient is positive, so this statement also follows from the empty sum when \(\mathcal L=0\). Substituting this bound into Euler’s identity proves (23). ◻

Proof. On \(U_\omega\) write \(\deg_\omega(x)\) for the enabled degree and put \(q(x)=d-\deg_\omega(x)\ge0\). There are no enabled edges to the removed set. Thus, for finitely supported complex \(\xi\) on \(U_\omega\), \[ \begin{split} \mathcal E(\xi) :=\langle\pi_\omega(T)\xi,\xi\rangle =\sum_{\{x,y\}\in E(G_\omega|_{U_\omega})} |\xi(x)-\xi(y)|^2 +\sum_{x\in U_\omega}q(x)|\xi(x)|^2. \end{split} \tag{34}\] All edge sums in the rest of this proof are over enabled unoriented edges on \(U_\omega\). For a finite set \(F\subseteq U_\omega\), its deficit is exactly \[d|F|-2|E(G_\omega|_F)| =|\partial_{G_\omega|_{U_\omega}}F|+\sum_{x\in F}q(x).\]

Set \(s(x)=|\xi(x)|\). Apply Lemma 16 to the finite level sets \(\{x:s(x)^2>t\}\) and integrate in \(t\ge0\). The layer-cake identity gives \[(c/2)\|\xi\|^2 \le\sum_{\{x,y\}}|s(x)^2-s(y)^2|+\sum_xq(x)s(x)^2.\] Cauchy–Schwarz, applied together to the edge terms and the vertex-potential terms, then gives \[\begin{align*} (c/2)\|\xi\|^2 &\le \left(\sum_{\{x,y\}}|s(x)-s(y)|^2+\sum_xq(x)s(x)^2\right)^{1/2} \left(\sum_{\{x,y\}}(s(x)+s(y))^2+\sum_xq(x)s(x)^2\right)^{1/2}\\ &\le\mathcal E(\xi)^{1/2}\sqrt{2d}\,\|\xi\|. \end{align*}\] For the first factor we used \(||\xi(x)|-|\xi(y)||\le|\xi(x)-\xi(y)|\). For the second we used \[\sum_{\{x,y\}}(s(x)+s(y))^2+\sum_xq(x)s(x)^2 \le\sum_x\bigl(2\deg_\omega(x)+q(x)\bigr)s(x)^2 \le2d\|\xi\|^2.\] If \(\xi\ne0\), division and squaring prove \(\mathcal E(\xi)\ge(c^2/(8d))\|\xi\|^2\); the zero vector satisfies the same inequality. Finite-support vectors are dense and the operator is bounded, so (32) holds on all of \(\ell^2(U_\omega)\). If \(U_\omega\) is empty, this assertion is vacuous.

On each valid copy \(P\) of type \(i\), the operator is its graph Laplacian \(dI-\mathop{\mathrm{Adj}}(P)\). Its kernel consists of constants, and on the orthogonal complement of constants it is at least \(\rho I\), by Proposition 7. The valid copies are disjoint isolated components. Decomposing \(\ell^2(\Gamma)\) into their component spaces and \(\ell^2(U_\omega)\) therefore shows that the full kernel is exactly \[\bigoplus_{P\text{ valid for }\omega}\mathbb C\mathbf 1_P,\] and that the operator is at least \(\varepsilon I\) on its orthogonal complement. These conclusions remain true for infinitely many valid components, because both lower bounds are uniform. The earlier bound \(\pi_\omega(T)\le2dI\) proves (33). ◻

Proof. Take the faithful direct sum of the representations \(\pi_\omega\). Lemma 17 gives the same positive constant \(\varepsilon\) in every summand, so its spectrum is contained in the closed set \(\{0\}\cup[\varepsilon,2d]\). Faithfulness preserves the spectrum of the self-adjoint element \(T\); hence \[\mathop{\mathrm{spec}}_{C_r^*(G_{\mathrm{sur}})}(T)\subseteq\{0\}\cup[\varepsilon,2d].\] Choose a continuous real-valued function \(\chi\) on \([0,2d]\) with \(\chi(0)=1\) and \(\chi=0\) on \([\varepsilon,2d]\), and set \(b_0=\chi(T)\) by continuous functional calculus. Since \(\chi^2=\chi\) on the spectrum, \(b_0\) is a projection in \(C_r^*(G_{\mathrm{sur}})\). This uses the ordinary C*-algebra functional calculus, with no passage to a von Neumann algebra.

Functional calculus commutes with each \(\pi_\omega\). The kernel description in Lemma 17 thus identifies \(\pi_\omega(b_0)\) as claimed, also when there are no valid copies or infinitely many of them. The normalized constant vector on a valid copy of type \(i\) is \(n_i^{-1/2}\mathbf 1_P\), so the diagonal of its rank-one projection at any vertex of \(P\) is \(1/n_i\). At vertices of \(U_\omega\) the diagonal is zero. Disjointness of the valid copies proves uniqueness and (35). ◻