If \(G\) is disconnected, let \(S\) be the vertex set of one connected component, so \(\emptyset \ne S\subsetneq V(G)\) and \(E(S,\bar S)=\emptyset \). Then \(h_G(S)=0\), hence \(h_G=0\). Conversely, if \(h_G=0\) then, since the minimum defining \(h_G\) ranges over finitely many nonempty proper subsets \(S\) and each denominator \(\min (\mathrm{vol}\, S,\mathrm{vol}\, \bar S){\gt}0\) (no isolated vertices), some \(S\) has \(|E(S,\bar S)|=0\). Then no edge joins \(S\) to \(\bar S\), so \(G\) is disconnected.

Choose an optimal cut \(C=E(A,B)\) achieving \(h_G\), separating \(G\) into \(A\) and \(B=\bar A\), so \(|C|=h_G\min (\mathrm{vol}\, A,\mathrm{vol}\, B)\). Define

Then \(\sum _v f(v)d_v=\dfrac {\mathrm{vol}\, A}{\mathrm{vol}\, A}-\dfrac {\mathrm{vol}\, B}{\mathrm{vol}\, B}=0\), so \(f\) is orthogonal to the degree vector and is admissible in the Rayleigh characterization of \(\lambda _1\). Only the edges of \(C\) contribute to the numerator, each with \((f(u)-f(v))^2=\bigl(\tfrac {1}{\mathrm{vol}\, A}+\tfrac {1}{\mathrm{vol}\, B}\bigr)^2\), while

Hence

For each \(i\), \(C_i=E(V_i,\bar V_i)\) with \(V_i=\{ v_1,\dots ,v_i\} \), so \(|C_i|/\min (\mathrm{vol}\, V_i,\mathrm{vol}\, \bar V_i)=h_G(V_i)\ge h_G\); taking the minimum gives \(\alpha \ge h_G\).

Since \(g\ge 0\) and \(g(v_i)\) is nondecreasing, \(g^2(v_i)\) is nondecreasing. For an edge \(\{ v_j,v_k\} \) with \(j{\lt}k\),

and this edge lies in \(C_i\) exactly for \(j\le i{\lt}k\). Summing over all edges and exchanging the order of summation,

By definition of \(\alpha \), \(|C_i|\ge \alpha \min \bigl(\sum _{j\le i}d_{v_j},\sum _{j{\gt}i}d_{v_j}\bigr)\). If \(g^2(v_{i+1})-g^2(v_i){\gt}0\) then \(g(v_{i+1}){\gt}0\), so \(\{ v_{i+1},\dots ,v_n\} \subseteq \{ g{\gt}0\} \) has volume \(\le \tfrac 12\mathrm{vol}\, G\le \sum _{j\le i}d_{v_j}\); hence the minimum equals \(\sum _{j{\gt}i}d_{v_j}\). Therefore

Writing \(a_i=g^2(v_i)\), \(S_i=\sum _{k{\gt}i}d_{v_k}\) (so \(S_{i-1}-S_i=d_{v_i}\), \(S_{n}=0\)), Abel summation and \(a_1=0\) give

Combining the last two displays yields the claim.

Let \(f\) be the harmonic eigenfunction of \(\mathcal L\) with eigenvalue \(\lambda _1\), satisfying \(\sum _{u\sim v}(f(v)-f(u))=\lambda _1 f(v)d_v\) for every \(v\). Order the vertices so that \(f(v_i)\le f(v_{i+1})\). Replacing \(f\) by \(-f\) if necessary we may assume

so \(V_+=\{ v:f(v)\ge 0\} \) has \(\mathrm{vol}\, V_+\le \tfrac 12\mathrm{vol}\, G\). Put \(g(x)=f(x)\) for \(x\in V_+\) and \(g(x)=0\) otherwise; then \(g\ge 0\) and \(\{ g{\gt}0\} \subseteq V_+\) has volume \(\le \tfrac 12\mathrm{vol}\, G\). Let \(E_+\) be the set of edges with at least one endpoint in \(V_+\). Multiplying the eigenvalue equation by \(f(v)\) and summing over \(v\in V_+\),

because for an edge inside \(V_+\) the two contributions combine to \((f(u)-f(v))^2=(g(u)-g(v))^2\), while a boundary edge \(\{ v,u\} \) with \(v\in V_+\), \(u\notin V_+\) (so \(f(u){\lt}0\)) contributes \(f(v)(f(v)-f(u))\ge f(v)^2=(g(v)-g(u))^2\), strictly for at least one edge as \(G\) is connected. Now apply the Cauchy–Schwarz inequality to the pairs \(|g(u)-g(v)|\) and \(|g(u)+g(v)|\):

Since \(\sum _{E_+}(g(u)+g(v))^2\le 2\sum _{E_+}(g^2(u)+g^2(v))\le 2\sum _v g^2(v)d_v\), and edges outside \(E_+\) contribute \(0\) to \(\sum |g^2(u)-g^2(v)|\),

using Lemma 73 for the co-area step and \(\alpha \ge h_G\).

Keep the notation of the proof of Theorem 74 and set

By Cauchy–Schwarz the numerator satisfies \(\sum _{E_+}(g(u)-g(v))^2\cdot \sum _{E_+}(g(u)+g(v))^2\ge (\sum _{E_+}|g^2(u)-g^2(v)|)^2\). Using

we obtain

the last step by Lemma 73. Hence \(W(2-W)\ge \alpha ^2\), i.e. \(W^2-2W+\alpha ^2\le 0\). Since \(W\le 1\), this forces \(W\ge 1-\sqrt{1-\alpha ^2}\), whence

Ordering the vertices by \(f\) as in Theorem 75, the cut \(C_{v_i}\) coincides with \(C_i\) and the two sums are \(\sum _{j\le i}d_{v_j}\) and \(\sum _{j{\gt}i}d_{v_j}\); thus the vertex-indexed \(\alpha \) equals the index-indexed \(\alpha \) there, and the bound is exactly the one established in that proof.

For any \(\emptyset \ne S\subsetneq V(G)\) with \(G\) connected, \(|E(S,\bar S)|\ge 1\), and \(\min (\mathrm{vol}\, S,\mathrm{vol}\, \bar S)\le \tfrac 12\mathrm{vol}\, G\), so \(h_G(S)\ge 2/\mathrm{vol}\, G\); minimizing gives \(h_G\ge 2/\mathrm{vol}\, G\). By the Cheeger inequality 74, \(\lambda _1{\gt}h_G^2/2\ge \tfrac 12(2/\mathrm{vol}\, G)^2=2/(\mathrm{vol}\, G)^2\). Since \(\mathrm{vol}\, G=\sum _v d_v\le n(n-1){\lt}n^2\), this is \({\gt}2/n^4\).

Fix \(\emptyset \ne S\subsetneq V(G)\). Each boundary edge \(\{ u,v\} \in E(S,\bar S)\) (with \(u\in S\), \(v\notin S\)) has its outside endpoint \(v\in \delta S\); hence the boundary edges are among the edges incident to \(\delta S\), and their number is at most \(\sum _{v\in \delta S}d_v=\mathrm{vol}\, \delta S\). Thus \(|E(S,\bar S)|\le \mathrm{vol}\, \delta (S)\), giving \(h_G(S)\le g_G(S)\). Taking minima, \(h_G\le g_G\).

By Lemma 78, \(g_G\ge h_G\), and by Lemma 72, \(2h_G\ge \lambda _1\); hence \(2g_G\ge 2h_G\ge \lambda _1\).

Follow the notation of Theorem 74: let \(f\) be the harmonic eigenfunction for \(\lambda _1\), \(V_+=\{ f\ge 0\} \), and \(f_+=g\) the function equal to \(f\) on \(V_+\) and \(0\) elsewhere. As there,

Construction of a flow. Consider the network with vertices \(\{ s,t\} \cup X\cup Y\) where \(X=V_+\) and \(Y\) is a copy of \(V(G)\), and directed edges: \((s,u)\) of capacity \((1+g_G)d_u\) for \(u\in X\); \((u,v)\) of capacity \(d_v\) whenever \(u\in X\), \(v\in Y\) and either \(\{ u,v\} \in E(G)\) or \(u,v\) label the same vertex; and \((v,t)\) of very large capacity for \(v\in Y\). For any cut \(C\) separating \(s\) and \(t\), let \(X_1=\{ x\in X:(s,x)\notin C\} \). Since \(C\) must block every \(s\)–\(t\) path through \(X_1\), its capacity is at least

using \(\mathrm{vol}\, \delta X_1\ge g_G\, \mathrm{vol}\, X_1\). As the cut consisting of all edges \((s,u)\) has capacity exactly \((1+g_G)\mathrm{vol}\, V_+\), the min-cut equals \((1+g_G)\mathrm{vol}\, V_+\). By Theorem 80 there is a flow \(F(u,v)\le \text{capacity}\) with, for each \(x\in X\) and \(y\in Y\),

Two inequalities. Using \(F(u,v)\le d_v\le d\) and the flow values, for each edge sum one gets

Also, since \(\sum _v F(u,v)-\sum _v F(v,u)\ge (1+g_G)d_u-d_u=g_G d_u\) for \(u\in V_+\),

Combination. By Cauchy–Schwarz applied to \(|f_+(u)-f_+(v)|\) and \(|F(u,v)(f_+(u)+f_+(v))|\),

(\(\ge \)). Given \(f\), choose \(c\) with \(\sum _{f(x){\lt}c}d_x\le \sum _{f(x)\ge c}d_x\) and \(\sum _{f(x)\le c}d_x{\gt}\sum _{f(x){\gt}c}d_x\) (a degree-weighted median), and set \(g=f-c\). Then for \(\sigma {\lt}0\), \(\sum _{g(x){\lt}\sigma }d_x\le \sum _{g(x)\ge \sigma }d_x\), and for \(\sigma {\gt}0\), \(\sum _{g(x){\lt}\sigma }d_x\ge \sum _{g(x){\gt}\sigma }d_x\). Put \(\tilde g(\sigma )=|\{ \{ x,y\} \in E(G): g(x)\le \sigma {\lt}g(y)\} |=|E(A_\sigma ,\bar A_\sigma )|\) with \(A_\sigma =\{ x:g(x)\le \sigma \} \). Each edge crosses exactly the levels between its endpoints, so

For \(\sigma {\lt}0\) the set \(A_\sigma \) has the smaller volume, so \(\tilde g(\sigma )\ge h_G\sum _{g(x){\lt}\sigma }d_x\); for \(\sigma {\gt}0\) the set \(\bar A_\sigma \) is smaller, so \(\tilde g(\sigma )\ge h_G\sum _{g(x){\gt}\sigma }d_x\). Hence

since \(\int _{-\infty }^0\mathbf1[g(x){\lt}\sigma ]d\sigma +\int _0^\infty \mathbf1[g(x){\gt}\sigma ]d\sigma =|g(x)|\). Thus \(\sup _c(\cdots )\ge h_G\) for every \(f\), so the infimum is \(\ge h_G\).

(\(\le \)). Let \(X\) achieve \(h_G=|E(X,\bar X)|/\mathrm{vol}\, X\) with \(\mathrm{vol}\, X\le \mathrm{vol}\, \bar X\), and set \(\psi (x)=1\) on \(X\), \(\psi (x)=-1\) off \(X\). Then \(\sum _{x\sim y}|\psi (x)-\psi (y)|=2|E(X,\bar X)|\) and, for \(c\in \mathbb {R}\), \(\sum _x|\psi (x)-c|d_x=|1-c|\mathrm{vol}\, X+|1+c|\mathrm{vol}\, \bar X\), minimized over \(c\) at \(c=1\) giving \(2\mathrm{vol}\, X\). Hence

so the infimum is \(\le h_G\). Combining the two directions proves (2.5).

First inequality. Let \(X\) be optimal, \(\mathrm{vol}\, X\le \mathrm{vol}\, \bar X\), and \(\alpha =\mathrm{vol}\, X/\mathrm{vol}\, G\). Set \(f=\mathbf1_X-\alpha \); then \(\sum _x f(x)d_x=(1-\alpha )\mathrm{vol}\, X-\alpha \, \mathrm{vol}\, \bar X=0\), so (2.6) holds. Its numerator is \(|E(X,\bar X)|\) and its denominator is \((1-\alpha )\mathrm{vol}\, X+\alpha \, \mathrm{vol}\, \bar X=2\, \mathrm{vol}\, X\, \mathrm{vol}\, \bar X/\mathrm{vol}\, G\), so the quotient equals \(h_G\cdot \mathrm{vol}\, G/(2\, \mathrm{vol}\, \bar X)\le h_G\) (as \(\mathrm{vol}\, \bar X\ge \mathrm{vol}\, G/2\)). Hence the infimum is \(\le h_G\).

Second inequality. Let \(f\) satisfy (2.6) and let \(c\) be the degree-weighted median from the proof of Theorem 82, so \(\sum _{x\sim y}|f(x)-f(y)|\ge h_G\sum _x|f(x)-c|d_x\). If \(c\le 0\), then for \(f(x)\ge 0\) one has \(|f(x)-c|\ge |f(x)|\), so

the last equality because \(\sum _x f(x)d_x=0\) forces \(\sum _{f\ge 0}f\, d_x=\tfrac 12\sum _x|f|d_x\). (If \(c\ge 0\) use \(f(x)\le 0\) symmetrically.) Therefore \(\sum _{x\sim y}|f(x)-f(y)|\ge \tfrac 12 h_G\sum _x|f(x)|d_x\), giving the second inequality.

For every \(S\), \((\min _v d_v)\min (|S|,|\bar S|)\le \min (\mathrm{vol}\, S,\mathrm{vol}\, \bar S)\le (\max _v d_v)\min (|S|,|\bar S|)\), since \((\min d)|T|\le \mathrm{vol}\, T\le (\max d)|T|\) for any \(T\). Dividing \(|E(S,\bar S)|\) by these gives \(\dfrac {h’(S)}{\max _v d_v}\le h_G(S)\le \dfrac {h’(S)}{\min _v d_v}\), i.e. \((\min d)h_G(S)\le h'(S)\le (\max d)h_G(S)\). Taking infima/minima over \(S\) (the inequalities hold pointwise) yields \((\min d)h_G\le h'_G\le (\max d)h_G\).

For every \(f\) and \(t\), \(\sum _v(f(v)-t)^2 d_v\le (\max _v d_v)\sum _v(f(v)-t)^2\), so the normalized Rayleigh quotient is at least \(1/\max _v d_v\) times the combinatorial one. By the Courant–Fischer min-max characterization of \(\lambda _i\) and \(\lambda '_i\), \(\lambda _i\ge \lambda '_i/\max _v d_v\), i.e. \(\lambda '_i\le \lambda _i\max _v d_v\); nonnegativity is clear.

Let \(X\) achieve \(h'_G\) with \(|X|\le |\bar X|\), and set \(f=1/|X|\) on \(X\), \(f=-1/|\bar X|\) on \(\bar X\), so \(\sum _v f(v)=0\). Only edges of \(E(X,\bar X)\) contribute to \(\sum _{u\sim v}(f(u)-f(v))^2=|E(X,\bar X)|(1/|X|+1/|\bar X|)^2\), while \(\sum _v f(v)^2=1/|X|+1/|\bar X|\). Hence

The argument mirrors Theorem 74 for \(L=T-A\) (counting measure). In the Cauchy–Schwarz step one bounds \(\sum _{u\sim v}(f(u)+f(v))^2\le 2\sum _v f(v)^2 d_v\le 2(\max _v d_v)\sum _v f(v)^2\); the extra factor \(\max _v d_v\) propagates into the denominator, yielding \(\lambda '_1\ge h_G'^2/(2\max _v d_v)\) in place of the sharper \(h_G^2/2\) of Theorem 74.

Repeat the proof of Theorem 82 with the measure \(w_x\) on vertices and \(w(x,y)\) on edges. Choosing \(c\) to be the \(w\)-weighted median of \(f\) and setting \(g=f-c\), the weighted co-area identity \(\sum _{x\sim y}|f(x)-f(y)|w(x,y)=\int _{-\infty }^\infty \tilde g_w(\sigma )\, d\sigma \) (with \(\tilde g_w(\sigma )=\sum _{g(x)\le \sigma {\lt}g(y)}w(x,y)\)) together with \(\tilde g_w(\sigma )\ge h(G,w)\min (\sum _{g{\lt}\sigma }w_x,\sum _{g{\gt}\sigma }w_x)\) gives \(\sup _c(\cdots )\ge h(G,w)\). Conversely the \(\pm 1\) indicator of an optimal \(S\) realizes the value \(h(G,w)\), giving \(\inf _f\sup _c(\cdots )\le h(G,w)\).

Apply Theorem 92 to the weight \(w_1\) with \(w_1(u,v)=1\) and \(w_1(x)=1\), for which \(h(G,w_1)=h'_G\).

We prove (2.9); the general case follows by induction on \(k\). Assume \(\lambda _G\le \lambda _H\). In \(G\otimes H\) the vertex \((u,v)\) has weight \(2d_u d_v\), an edge \(\{ u,u'\} \in E(G)\) gives edges of weight \(d_v\), and an edge \(\{ v,v'\} \in E(H)\) gives edges of weight \(d_u\).

Upper bound. Let \(f\) be the harmonic eigenfunction of \(G\) for \(\lambda _G\) (so \(\sum _u f(u)d_u=0\)), and set \(f_0(u,v)=f(u)\). Its Rayleigh quotient in \(G\otimes H\) is

so \(\lambda _{G\otimes H}\le \lambda _G/2\).

Lower bound. Let \(g\) be the harmonic eigenfunction of \(G\otimes H\) achieving \(\lambda _{G\otimes H}\). Put

Since \(g_v\) is the degree-weighted mean of \(g(\cdot ,v)\), the cross term vanishes and

For the numerator, the variational definition of \(\lambda _G\) gives \(\sum _{u\sim u'}(g(u,v)-g(u',v))^2\ge \lambda _G\sum _u(g(u,v)-g_v)^2 d_u\); and by convexity \(\sum _u d_u(g(u,v)-g(u,v'))^2\ge \mathrm{vol}\, G\, (g_v-g_{v'})^2\), followed by \(\sum _{v\sim v'}(g_v-g_{v'})^2\ge \lambda _H\sum _v(g_v-c)^2 d_v\). Writing \(A=\sum _{u,v}(g(u,v)-g_v)^2 d_u d_v\) and \(B=\mathrm{vol}\, G\sum _v(g_v-c)^2 d_v\),

Together with the upper bound, \(\lambda _{G\otimes H}=\lambda _G/2=\tfrac 12\min (\lambda _G,\lambda _H)\).

We prove (2.11); the general case is analogous. Assume \(h_G\le h_H\).

Upper bound. Let \(f\) achieve \(h(G)\) in (2.7) and set \(f_0(u,v)=f(u)\). Its quotient (2.7) in \(G\otimes H\) equals \(h_G/2\), so \(h_{G\otimes H}\le h_G/2\).

Lower bound. Adopt the notation \(g,g_v,c\) of the proof of Theorem 98 but with the \(\ell _1\)-form (2.7). Using \(\sum _{u,v}(g(u,v)-c)\, 2d_ud_v\) split at \(g_v\), the characterization of \(h_G\) from Theorem 92 for the inner \(G\)-differences and of \(h_H\) for the \(g_v\)-differences, together with the factor-\(\tfrac 12\) estimates of Corollary 83,

where \(P=\sum _{u,v}|g(u,v)-g_v|\, 2d_u d_v\) and \(Q=\sum _{u,v}|g_v-c|\, 2d_u d_v\), and \(h_G\le h_H\). Hence \(h_{G\otimes H}\ge h_G/4=\tfrac 14\min (h(G),h(H))\).