From a Cut to a Cheeger Constant
Conductance measures how many edges leave a set relative to the number of edges available from its vertices. A set with few outgoing edges compared with its volume is a bottleneck for movement through the graph. For small graphs, the definition gives a direct way to find such bottlenecks: enumerate the eligible vertex sets, compute their conductances, and take the minimum. The resulting value can then be compared with the spectral gap of the random walk.
Throughout, graphs are finite and simple. For a set \(S\subseteq V(G)\), let \(\partial S\) be the set of edges with exactly one endpoint in \(S\), and let \(\operatorname{vol}(S)=\sum_{v\in S}\deg(v)\). We consider a \(d\)-regular graph with \(d\geq 1\), so \(\operatorname{vol}(S)=d|S|\). A set is eligible in the minimum when it is nonempty and has volume at most half the total volume.
The half-volume restriction avoids counting both sides of the same cut. Indeed, \(\partial S=\partial(V(G)\setminus S)\), and in a regular graph the smaller of these two sides has at most half the vertices. Thus, for an even number of vertices, sets of exactly half the vertices are included; sets larger than half are not needed. The empty set is excluded because its conductance would have a zero denominator.
Write the eigenvalues of the simple random walk transition matrix \(P=\mathbf{A}(G)/d\) in decreasing order as \(1=\mu_1\geq\mu_2\geq\cdots\), counting multiplicity. The (top) spectral gap is \(\gamma=1-\mu_2\). This is not an absolute-value gap: a negative eigenvalue does not determine \(\mu_2\). For the finite \(d\)-regular graphs considered here, the Cheeger inequalities are
These are the lower Cheeger bound by level sets and the upper Cheeger bound from a cut, whose proofs belong to the earlier material on those bounds. Here we use them in their stated regular-graph form: the denominator in conductance is \(d|S|\), and the gap uses the second-largest eigenvalue of \(P\). The inequalities apply to disconnected regular graphs as well; then both the Cheeger constant and the top gap are zero.
A Direct Enumeration Method
For a \(d\)-regular graph, a useful way to calculate a boundary is to count the edges internal to the selected set first. Let \(e(S)\) be the number of edges with both endpoints in \(S\). The degree sum over \(S\) counts each internal edge twice and each boundary edge once, so
Proof. Sum the degrees of the vertices in \(S\). Each edge with both endpoints in \(S\) contributes two to this sum; each edge with exactly one endpoint in \(S\) contributes one; and every other edge contributes zero. Therefore \(d|S|=2e(S)+|\partial S|\), which rearranges to the claimed identity. The argument also covers \(S=\varnothing\), when both sides are zero. \(\square\)
This identity is a checking tool, not a replacement for specifying the boundary: one may also count directly the edges joining \(S\) to its complement. A small-graph calculation can be organized as follows.
List nonempty sets with \(|S|\leq n/2\); do not include the empty set.
Use the edge list, or compute \(d|S|-2e(S)\), and divide by \(d|S|\).
Record every set whose ratio equals the least value, including ties.
Find \(\mu_2\), calculate \(\gamma=1-\mu_2\), and evaluate both bounds using the computed \(h(G)\).
The search is finite, so this procedure is an exact method, not a heuristic. At each step every eligible set is either evaluated or excluded only because it is empty or too large. Since the minimum of a finite list of real numbers is one of its entries, the least computed ratio is exactly \(h(G)\), and the sets giving that ratio are precisely the minimizers. \(\square\)
Worked Computations
Worked Example: The Cycle \(C_4\)
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). This is a 2-regular graph. Eligible sets have size one or two. A singleton has two boundary edges, so its conductance is \(2/(2\cdot1)=1\). A pair of adjacent vertices has two boundary edges and conductance \(2/(2\cdot2)=1/2\). A pair of opposite vertices has four boundary edges and conductance \(4/(2\cdot2)=1\). These cases exhaust the eligible sets: every pair is either adjacent or opposite. Thus \(h(G)=1/2\), attained by each adjacent pair.
For the spectral gap, the adjacency eigenvalues of a cycle \(C_4\) are \(2\cos(2\pi k/4)\) for \(k=0,1,2,3\), giving \(2,0,-2,0\). Dividing by the degree \(2\), the eigenvalues of \(P\) in decreasing order are \(1,0,0,-1\). Hence \(\gamma=1-0=1\). The lower bound is \(h(G)^2/2=(1/2)^2/2=1/8=0.125\); the upper bound is \(2h(G)=2(1/2)=1\). The check is \(0.125\leq1\leq1\), with equality in the upper bound.
Check: For the minimizing pair \(S=\{1,2\}\), there are two internal edges? Its only internal edge is \(12\), so \(e(S)=1\). The boundary identity gives \(|\partial S|=2\cdot2-2\cdot1=2\), agreeing with the direct count of edges \(23\) and \(41\).
Worked Example: The Complete Graph \(K_4\)
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). Its degree is \(3\), and eligible sets again have size one or two. Each singleton has boundary size \(3\), giving conductance \(3/(3\cdot1)=1\). Each pair has two internal vertices joined by one edge; each of those vertices has two neighbors outside the pair, so the boundary size is \(4\). Its conductance is \(4/(3\cdot2)=2/3\). All pairs therefore attain the minimum, and \(h(G)=2/3\).
The adjacency matrix of \(K_4\) has eigenvalue \(3\) on the all-ones vector. Every vector whose coordinates sum to zero is sent to its negative, because each coordinate of the adjacency product is the sum of all the other coordinates. That subspace has dimension three, so the other three adjacency eigenvalues are \(-1\). After dividing by \(3\), the eigenvalues of \(P\) are \(1,-1/3,-1/3,-1/3\), and \(\gamma=1-(-1/3)=4/3\).
The lower Cheeger bound is \((2/3)^2/2=4/9/2=2/9\), and the upper bound is \(2(2/3)=4/3\). Thus \(2/9\leq4/3\leq4/3\); the upper bound is attained. As a boundary check, for \(S=\{1,2\}\), the degree sum is \(3\cdot2=6\), and the one internal edge contributes \(2\), leaving \(6-2=4\) boundary edges, as counted directly.
Worked Example: The Complete Bipartite Graph \(K_{3,3}\)
Let \(X=\{a,b,c\}\), \(Y=\{x,y,z\}\), \(V=X\cup Y\), and \(E=\{uv:u\in X,\ v\in Y\}\). This definition gives all nine edges between the two parts and no edges within either part; the graph is 3-regular. To enumerate conductances, put \(a_0=|S\cap X|\) and \(b_0=|S\cap Y|\). For an eligible set, \(1\leq a_0+b_0\leq3\). There are \(a_0b_0\) internal edges, so the boundary identity gives \(3(a_0+b_0)-2a_0b_0\).
| \(a_0+b_0\) | Possible \((a_0,b_0)\) | Conductance values |
|---|---|---|
| 1 | \((1,0),(0,1)\) | \(1,1\) |
| 2 | \((2,0),(1,1),(0,2)\) | \(1,2/3,1\) |
| 3 | \((3,0),(2,1),(1,2),(0,3)\) | \(1,5/9,5/9,1\) |
For example, for type \((2,1)\), the boundary size is \(3\cdot3-2\cdot2\cdot1=9-4=5\), and the denominator is \(3\cdot3=9\), giving conductance \(5/9\). The table covers every possible type, so \(h(G)=5/9\), attained by sets with two vertices in one part and one in the other.
The adjacency matrix has block form with zero blocks within the parts and an all-ones \(3\)-by-\(3\) block between them. The all-ones vector on all six vertices has eigenvalue \(3\); the vector equal to \(1\) on \(X\) and \(-1\) on \(Y\) has eigenvalue \(-3\). A vector whose coordinates sum to zero separately on \(X\) and on \(Y\) is sent to zero. These vectors form a four-dimensional space, so the remaining four eigenvalues are zero. Thus \(P\) has eigenvalues \(1,0,0,0,0,-1\), and \(\gamma=1-0=1\).
The lower bound is \((5/9)^2/2=25/81/2=25/162\), approximately \(0.1543\). The upper bound is \(2(5/9)=10/9\), approximately \(1.1111\). Therefore \(25/162\leq1\leq10/9\), or approximately \(0.1543\leq1\leq1.1111\). For a minimizing set of type \((2,1)\), the boundary identity gives \(3\cdot3-2\cdot2=9-4=5\), agreeing with the five crossing edges.
Reading the Results Carefully
These examples show that a minimum-conductance cut and a spectral gap answer related but different questions. The cut calculation searches over vertex sets and finds the exact bottleneck for the chosen graph. The gap is a global eigenvalue quantity. The Cheeger inequalities constrain one using the other, but they need not give equality on both sides. For \(C_4\) and \(K_4\), the upper bound is exact; for \(K_{3,3}\), the computed gap lies strictly between the two bounds.
Common mistake: omitting the degree from the denominator. In \(K_4\), a two-vertex set has four boundary edges. Dividing only by its size gives \(4/2=2\), but this is not its conductance. The volume is \(3\cdot2=6\), so the correct value is \(4/6=2/3\). Using the wrong value would incorrectly report the Cheeger constant as \(2\), rather than \(2/3\), and would make the stated Cheeger comparisons meaningless for the defined normalization. Always divide by volume, which is \(d|S|\) for a \(d\)-regular graph.
For larger graphs, exhaustive enumeration can become expensive because the number of vertex sets grows rapidly. For the small explicit graphs here, however, the method has two advantages: it certifies the minimum by checking all eligible set types, and it displays which cuts attain it. When there are symmetries, group sets by a simple description such as size or the number of vertices selected from each part, but verify that those types still cover every eligible set.
Check Your Understanding
Use the definitions and calculations above; when computing a Cheeger constant, include every eligible set type.
- In \(C_6\), compare the conductance of a singleton, a consecutive pair, and a consecutive triple. Which of these is smallest?
- For a \(d\)-regular graph and a set \(S\), explain why each internal edge contributes two to the degree sum over \(S\), while each boundary edge contributes one.
- In \(K_{2,2}\), enumerate eligible set types by their counts from the two parts and find \(h(G)\) and all types attaining it.
- If a \(d\)-regular graph has \(h(G)=1/3\) and spectral gap \(\gamma=1/2\), check whether both Cheeger inequalities hold.
- Why are sets larger than half the vertices unnecessary when minimizing conductance in a regular graph?