Parts (a) and (b) follow from the variational principle (Lemma 309): \(f\) is a stationary point of the Rayleigh quotient in (8.3). Setting \(\partial /\partial f(x)=0\) at an interior vertex \(x\in S\) (which appears both in the numerator through the edges of \(S^{*}\) incident to \(x\) and in the denominator with weight \(d_x\)) yields \(\sum _{y:\{ x,y\} \in S^{*}}(f(x)-f(y))=\lambda f(x)d_x\), which is (a). A vertex \(x\in \delta S\) appears only in the numerator (it carries no denominator weight); setting \(\partial /\partial f(x)=0\) gives \(\sum _{y:\{ x,y\} \in \partial S}(f(x)-f(y))=0\), which is (b); dividing by \(d'_x\) and solving for \(f(x)\) gives the averaging form.

For (c), sum \(\mathcal{L}f\) against \(h\) over \(S\) and reorganize by edges. Writing \(\widetilde{\mathcal L}f(x)=\sum _{y:\{ x,y\} \in S^{*}}(f(x)-f(y))\) for all \(x\in S\cup \delta S\), we have

since each edge \(\{ x,y\} \in S^{*}\) contributes \(h(x)(f(x)-f(y))+h(y)(f(y)-f(x))\). Splitting the right side over \(x\in S\) and \(x\in \delta S\), the terms with \(x\in \delta S\) vanish by part (b), while for \(x\in S\) we have \(\widetilde{\mathcal L}f(x)=\mathcal Lf(x)\). Hence the right side equals \(\sum _{x\in S}h(x)\mathcal Lf(x)\), proving (c).

For \(g:S\to \mathbb {R}\) let \(u=NT^{-1/2}g\) be its Neumann extension to \(S\cup \delta S\). By construction \(u\) satisfies the Neumann condition on \(\delta S\), so by Lemma 317(c) the quadratic form \(\langle u,L_{S\cup \delta S}u\rangle =\sum _{\{ x,y\} \in S^{*}}(f(x)-f(y))^2\) with \(f=T^{-1/2}u|_S\) agrees with the numerator of (8.3). Hence

which is precisely the Rayleigh quotient of (8.3)/(8.4). By the min–max principle (Lemma 309) applied to the symmetric matrix \(\mathcal N_S\), its ordered eigenvalues equal the successive infima \(\lambda _{S,i}\). The constant function \(f\equiv 1\) gives a zero of the numerator, so \(g_0=T^{1/2}\mathbf1|_S\) satisfies \(\mathcal N_S g_0=0\), giving eigenvalue \(0\). If \(S\) is connected, the numerator \(\sum _{\{ x,y\} \in S^{*}}(f(x)-f(y))^2\) vanishes only for \(f\) constant on \(S\) (and its Neumann extension), so the \(0\)-eigenspace is one-dimensional and the remaining \(|S|-1\) eigenvalues are positive.

Expanding, \(\sum _{x\sim z}(f(x)-f(z))^2=\sum _{x\sim z}f^2(x)-2f(z)\sum _{x\sim z}f(x)+d'_z f^2(z)\). By the Neumann rule \(\sum _{x\sim z,\, x\in S}f(x)=d'_z f(z)\), so the middle term is \(-2d'_z f^2(z)\) and the total is \(\sum _{x\sim z}f^2(x)-d'_z f^2(z)\).

The walk \(P\) is reversible with respect to \(\pi (x)=d_x/\mathrm{vol}\, S\), so \(I-P\) is self-adjoint on \(\ell ^2(S,\pi )\) and its eigenvalues are \(1-\rho _i\); by the min–max principle (Lemma 309),

Extend \(f\) from \(S\) to \(\delta S\) by the Neumann rule \(f(z)=\frac1{d'_z}\sum _{y\sim z,\, y\in S}f(y)\). Using the two contributions of \(P\),

The first bracketed sum (over ordered pairs) equals \(2\sum _{\{ x,y\} \subseteq S}(f(x)-f(y))^2\). For each \(z\), the reflection sum equals \(\frac1{d'_z}\cdot 2\bigl[d'_z\sum _{x\sim z}f^2(x)-(\sum _{x\sim z}f(x))^2\bigr] =2\bigl[\sum _{x\sim z}f^2(x)-d'_z f^2(z)\bigr]\), where we used \(\sum _{x\sim z}f(x)=d'_z f(z)\); by Lemma 321 this equals \(2\sum _{x\sim z,\, x\in S}(f(x)-f(z))^2\), i.e. twice the sum over the boundary edges \(\{ x,z\} \in \partial S\). Therefore

so the Rayleigh quotient of \(I-P\) equals exactly the Neumann Rayleigh quotient of (8.3). Matching the min–max characterizations of the two symmetric operators gives \(1-\rho _i=\lambda _{S,i}\), i.e. \(\rho _i=1-\lambda _{S,i}\). (If one does not extend \(f\) harmonically, applying the Cauchy–Schwarz inequality \((\sum _{y\sim z}f(y))^2\le d'_z\sum _{y\sim z}f^2(y)\) (Lemma 310) to the reflection term reproduces the book’s chain of inequalities \(1-\rho \ge \cdots \ge \lambda _S\).)

Upper bound on \(\lambda _1^{(D)}\). Take the test function \(f\equiv 1\) on \(S\) and \(f\equiv 0\) on \(\delta S\); then \(f\in D^{*}\) and \(f\ne 0\). In the numerator only edges of \(\partial S\) contribute (each with \((1-0)^2=1\)) while edges inside \(S\) contribute \(0\), so the numerator is \(|\partial S|\); the denominator is \(\sum _{x\in S}1\cdot d_x=\mathrm{vol}\, S\). Hence \(\lambda _1^{(D)}\le |\partial S|/\mathrm{vol}\, S\). Since each edge of \(\partial S\) contributes exactly one endpoint to the degree sum \(\mathrm{vol}\, S\) and internal edges contribute two, \(\mathrm{vol}\, S\ge |\partial S|\), giving \(|\partial S|/\mathrm{vol}\, S\le 1\).

Positivity. If \(\lambda _1^{(D)}=0\), some nonzero \(f\in D^{*}\) has \(\sum _{\{ x,y\} \in S^{*}}(f(x)-f(y))^2=0\), so \(f\) is constant along every edge of \(S^{*}\). As \(S\) is connected and joined to \(\delta S\) (where \(f=0\)) by the non-empty boundary \(\partial S\), this forces \(f\equiv 0\) on \(S\), a contradiction. Hence \(\lambda _1^{(D)}{\gt}0\), and all \(\lambda _i^{(D)}{\gt}0\).

Upper bound \(\lambda _i^{(D)}\le 2\). For \(f\in D^{*}\), extend \(f\) by \(0\) to all of \(V\); then \(\langle f,\mathcal L_S f\rangle =\langle f,\mathcal Lf\rangle \) where \(\mathcal L\) is the host Laplacian. Since every eigenvalue of \(\mathcal L\) lies in \([0,2]\) (Lemma 30), the Rayleigh quotient \(\langle f,\mathcal Lf\rangle /\langle f,f\rangle \le 2\); taking min–max over \(D^{*}\) gives \(\lambda _i^{(D)}\le 2\).

Statement (1) is the stationarity (Euler–Lagrange) condition for the Rayleigh quotient (8.7) and follows from the variational principle (Lemma 309). For (2), expand the edge sum:

The inner sum over \(x\in S\) equals \(\sqrt{d_x}\, \mathcal Lg(x)\) by (1), giving \(\sum _{x\in S}h(x)\mathcal Lg(x)\); the terms with \(x\in \delta S\) carry a factor \(g(x)/\sqrt{d_x}=0\) (Dirichlet condition), hence vanish:

This proves (2).

By Lemma 325 (with \(g=f\) extended by \(0\) on \(\delta S\)), \(\mathcal Lf(x)=\mathcal L_S f(x)\) for \(x\in S\). Thus the eigenvalue problem (8.7) for \(f\in D^{*}\) is exactly the eigenvalue problem for the symmetric matrix \(\mathcal L_S\), and its eigenvalues are the Dirichlet eigenvalues \(\lambda _i^{(D)}\). By Proposition 324 each \(\lambda _i^{(D)}{\gt}0\), so \(\mathcal L_S\) is positive definite and in particular nonsingular. The determinant is the product of eigenvalues, giving \(\det \mathcal L_S=\prod _i\lambda _i^{(D)}\).

The columns of \(B\) indexed by the edges of a cycle are linearly dependent: orient the cycle and take coefficients \(\pm 1\) along it. At each row \(x\in S\) that lies on the cycle there are exactly two incident cycle-edges, whose entries \(\pm 1/\sqrt{d_x}\) cancel; vertices of \(\delta S\) index no rows, so they impose no constraint. Hence a nontrivial combination of the cycle columns is \(0\), making the square submatrix \(B_X\) singular, so \(\det B_X=0\).

Let \(Y\) be such a component. If \(Y\) contains more than one vertex of \(\delta S\), then \(|V(Y)\cap S|\le |V(Y)|-2\le |E(Y)|-1\) (since a connected graph has \(|E(Y)|\ge |V(Y)|-1\)). The columns of \(B\) indexed by the edges of \(Y\) have nonzero entries only in the rows indexed by \(V(Y)\cap S\) (boundary vertices are not rows), i.e. they lie in a space of dimension at most \(|E(Y)|-1\). Thus the \(|E(Y)|\) columns are linearly dependent, and any square submatrix \(B_X\) containing them has \(\det B_X=0\).

By Lemmas 328 and 329 we may assume the edges of \(X\) form a forest in which each connected component contains exactly one vertex of \(\delta S\). Then there is a leaf edge whose column has a single nonzero entry, say \((x_1,e_1)\) with \(x_1\in S\) (a pendant vertex of \(S\) attached by \(e_1\)). Expanding the determinant along that column, \(|\det B_X|=\frac{1}{\sqrt{d_{x_1}}}\, |\det B_X^{(1)}|\), where \(B_X^{(1)}\) is the submatrix on rows \(S\setminus \{ x_1\} \) and columns \(X\setminus \{ e_1\} \). Removing one pendant vertex and its edge at a time preserves the rooted-forest structure, and after \(|S|\) steps we obtain \(|\det B_X|=\prod _{x\in S}1/\sqrt{d_x}\).

Let \(B\) be the incidence matrix of Lemma 328. A direct computation gives \(\mathcal L_S=BB^{*}\) (equation (8.8)): the \((x,x)\) entry is \(\sum _{e\ni x}1/d_x=1\) and the \((x,y)\) entry for \(x\sim y\) is \(-1/\sqrt{d_xd_y}\). By the Cauchy–Binet formula (Lemma 312),

where \(X\) ranges over all \(|S|\)-element sets of edges of \(S^{*}\) and \(B_X\) is the \(|S|\times |S|\) submatrix on those columns. By Lemma 328, terms whose \(X\) contains a cycle vanish; by Lemma 329, terms whose \(X\) has a component with two boundary vertices vanish. The surviving \(X\) are exactly the rooted spanning forests of \(S\), and for each, \(\det B_X\det B_X^{*}=(\det B_X)^2=\prod _{x\in S}1/d_x\) by Lemma 330. Therefore

which rearranges to the stated count.

With \(S=V\setminus \{ v\} \), a rooted spanning forest \(F\) has vertex set \(V\), is acyclic, and has each component containing exactly one vertex of \(\delta S=\{ v\} \); hence \(F\) has a single component containing \(v\), i.e. \(F\) is a spanning tree of \(G\). Conversely each spanning tree, rooted at \(v\), is such an \(F\). Thus Theorem 331 counts spanning trees; unwinding the normalization \(\mathcal L_S=T^{-1/2}(T-A)_S T^{-1/2}\) shows this count is the principal cofactor of \(L=T-A\), which is Kirchhoff’s classical matrix-tree theorem.

\(H(f)\) is a quadratic function of the free variables \(\{ f(x):x\in S\} \) (the values on \(\delta S\) being fixed to \(\sigma \)). Its stationarity condition \(\partial H/\partial f(x)=2\sum _{y\sim x}(f(x)-f(y))=0\) for each \(x\in S\) is exactly the discrete-harmonic equation. The Hessian of \(H\) in the free variables is \(2\mathcal L_S\) (in the unnormalized/normalized sense of Corollary 326), which is positive definite since \(\delta S\ne \emptyset \) and \(S\) is connected; hence the quadratic has a unique minimizer \(f_0\), determined by \(\sigma \).

Let \(f_0\) be the harmonic minimizer of Lemma 334. For any \(g\) with \(g|_{\delta S}=\sigma \) write \(f=g-f_0\); then \(f\) satisfies the Dirichlet condition \(f|_{\delta S}=0\). Expanding,

The cross term equals \(2\sum _{x\in S}f(x)\sum _{y\sim x}(f_0(x)-f_0(y))=0\): the boundary contributions drop because \(f=0\) on \(\delta S\), and the interior sum vanishes by harmonicity of \(f_0\). Hence \(H(g)=H(f)+H(f_0)\) and

Expressing \(f\) in an orthonormal eigenbasis \(\{ \phi _i\} \) of \(\mathcal L_S\), \(f=\sum _i x_i\phi _i\), we get \(H(f)=\sum _i\lambda _i x_i^2\) (with \(\lambda _i\) the Dirichlet eigenvalues, by Corollary 326). Then by the Gaussian integral (Lemma 311),

which gives the stated formula, using \(\det \mathcal L_S=\prod _i\lambda _i\).