Volume, Boundary and Conductance
A cut separates a graph into a vertex set and its complement. The number of edges crossing the cut records how many connections leave the set, but it does not account for how many edges are available inside the set. Conductance compares the crossing edges with the total degree in the set. This distinction matters especially when degrees are unequal, and it makes conductance a natural measure of bottlenecks for random walks on graphs.
Throughout, graphs are finite, undirected and simple. For a set \(S\subseteq V(G)\), write \(\partial S\) for the set of edges with exactly one endpoint in \(S\), and write \(E(S)\) for the edges with both endpoints in \(S\). The volume of \(S\) is the sum of its vertex degrees.
The boundary size \(|\partial S|\) counts edges, not vertices. Every edge in \(E(S)\) contributes two to the sum of degrees in \(S\), while every edge in \(\partial S\) contributes one. Thus
Proof. Sum \(\deg(v)\) over \(v\in S\), counting incidences between vertices of \(S\) and edges. An edge with both endpoints in \(S\) contributes two incidences; an edge with exactly one endpoint in \(S\) contributes one; an edge with no endpoint in \(S\) contributes none. These are all possibilities, so the sum is \(2|E(S)|+|\partial S|\). \(\square\)
The condition \(0<\operatorname{vol}(S)\) is essential: a set with zero volume would make the denominator zero. For a graph with at least one edge, the minimum is over a nonempty collection. Indeed, choose an edge \(uv\). The singleton \(\{u\}\) has positive volume, and \(\deg(u)\le |E(G)|=\operatorname{vol}(V(G))/2\), since the edges incident to \(u\) are among all the edges. Hence \(\{u\}\) is eligible.
The use of half the total volume removes the need to count both sides of a cut. The boundary of \(S\) equals the boundary of its complement, but the denominators can differ. If both sides of a cut have positive volume, the side with smaller volume is eligible. If one side has zero volume, that side is excluded; it is not valid to use a zero-volume side as a candidate. This qualification is important in graphs with isolated vertices.
Conductance and Edge Expansion
For a nonempty vertex set \(S\), the edge expansion of the set is the number of boundary edges per vertex, \(|\partial S|/|S|\). For a graph with \(n\ge2\), define its edge expansion by minimizing over sets of at most half the vertices:
This is an unnormalized edge expansion: its denominator is the number of vertices, not the volume. Conductance instead uses the sum of degrees. The two measures coincide up to a factor in a regular graph.
Proof. In a \(d\)-regular graph, each set \(S\) has volume \(d|S|\), and the whole graph has volume \(dn\). Therefore \(0<\operatorname{vol}(S)\le\operatorname{vol}(V(G))/2\) holds exactly when \(0<d|S|\le dn/2\), or equivalently \(0<|S|\le n/2\), since \(d>0\). On every such set, \[ \Phi(S)=\frac{|\partial S|}{d|S|} =\frac{1}{d}\frac{|\partial S|}{|S|}. \] The eligible sets in the two minima are therefore identical, and every conductance ratio is the corresponding edge-expansion ratio divided by \(d\). Taking the minima gives \(\Phi(G)=h_E(G)/d\). \(\square\)
For an irregular graph, dividing edge expansion by one fixed degree does not generally recover conductance: different sets can have very different volumes. The volume denominator is what makes the definition sensitive to the degree distribution within the set.
Worked Cut Calculations
Worked Example: A Cut in a Cycle
Let \(G=C_6\), with \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,23,34,45,56,61\}\). Calculate the conductance of \(S=\{1,2,3\}\), and then find \(\Phi(G)\).
Each vertex has degree \(2\), so \(\operatorname{vol}(S)=\deg(1)+\deg(2)+\deg(3)=2+2+2=6\). The edges \(12\) and \(23\) lie inside \(S\); the crossing edges are \(34\) and \(61\). Thus \(|\partial S|=2\), and \(\Phi(S)=2/6=1/3\).
To check that this is the graph minimum, \(C_6\) is 2-regular, so an eligible set has \(1\le |S|\le3\). For such an \(S\), the induced edges form a union of paths, because a proper subset of the vertices of a cycle cannot contain the whole cycle. If \(k=|S|\), then \(|E(S)|\le k-1\). The volume-boundary identity gives \(|\partial S|=2k-2|E(S)|\ge2\). Hence \(\Phi(S)\ge2/(2k)=1/k\ge1/3\), since \(k\le3\). The chosen set attains \(1/3\), so \(\Phi(G)=1/3\).
Check: The selected set has volume \(6\), the total volume is \(6\cdot2=12\), and \(6\le12/2\), so it is eligible. Its two boundary edges give \(2/6=1/3\), as calculated.
Worked Example: Finding Conductance in \(K_{3,3}\)
Let \(G=K_{3,3}\), with parts \(A=\{a_1,a_2,a_3\}\) and \(B=\{b_1,b_2,b_3\}\); its edge set consists of all nine edges \(a_i b_j\), for \(1\le i,j\le3\). Every vertex has degree \(3\), so the total volume is \(6\cdot3=18\). For an eligible set \(S\), let \(x=|S\cap A|\) and \(y=|S\cap B|\). Eligibility is \(0<x+y\le3\).
There are \(3x\) incidences from the selected vertices of \(A\), and \(3y\) from the selected vertices of \(B\). Each edge internal to \(S\) is counted twice in that sum; there are \(xy\) such edges. Therefore \(|\partial S|=3x+3y-2xy\), while \(\operatorname{vol}(S)=3(x+y)\). For \(x+y=1\), the ratio is \(3/3=1\). For \(x+y=2\), the possibilities are \((x,y)=(2,0),(1,1),(0,2)\): their boundary sizes are \(6,4,6\), and their volume is \(6\), giving ratios \(1,2/3,1\). For \(x+y=3\), the possibilities \((3,0),(2,1),(1,2),(0,3)\) give boundary sizes \(9,5,5,9\), respectively, and each has volume \(9\). Their ratios are \(1,5/9,5/9,1\). Thus the minimum is \(5/9\), attained when the set contains one vertex from one part and two from the other. Consequently \(\Phi(K_{3,3})=5/9\).
Check: The graph has \(3\cdot3=9\) edges, and the sum of the six degrees is \(6\cdot3=18=2\cdot9\). For a minimizing set with \(x=1,y=2\), the boundary formula gives \(3+6-2(1)(2)=5\), and its volume is \(3(1+2)=9\), confirming \(5/9\).
Worked Example: An Isolated Vertex and a Zero-Volume Cut
Let \(G\) have \(V(G)=\{a,b,c,z\}\) and \(E(G)=\{ab,bc,ca\}\). Thus \(a,b,c\) form a triangle and \(z\) is isolated. Each of \(a,b,c\) has degree \(2\), and \(\deg(z)=0\), so the total volume is \(6\). Eligible sets must have positive volume at most \(3\).
A set of positive volume contains at least one triangle vertex. One triangle vertex contributes volume \(2\); two or three contribute volume \(4\) or \(6\), respectively, which is too large. Thus every eligible set contains exactly one of \(a,b,c\), with either choice of including \(z\). For example, take \(S=\{a,z\}\). Its volume is \(2+0=2\), and its boundary edges are \(ab\) and \(ac\), so \(\Phi(S)=2/2=1\). Every eligible set has the same ratio: adding \(z\) changes neither the volume nor the boundary, and each single triangle vertex has two boundary edges. Hence \(\Phi(G)=1\).
The cut with sides \(\{z\}\) and \(\{a,b,c\}\) has a side of volume zero. Its boundary has size zero, but the expression \(0/0\) is undefined, so this side is not eligible and does not make the graph conductance zero.
Check: For \(S=\{a,z\}\), the total volume \(6\) gives the threshold \(6/2=3\); the set has volume \(2\), so it is eligible. Its two crossing edges and volume \(2\) give \(2/2=1\). In contrast, \(\operatorname{vol}(\{z\})=0\), which fails the strict positive-volume condition.
Why Conductance Is Useful
In a \(d\)-regular graph, conductance also has a direct one-step random-walk interpretation. Start at a vertex chosen uniformly from a set \(S\), then choose one of its \(d\) neighbors uniformly. There are \(d|S|\) equally likely choices of a starting vertex and a next vertex. Each edge in \(\partial S\) gives exactly one such choice that leaves \(S\), namely the choice starting at its endpoint in \(S\). Therefore the probability of leaving \(S\) in one step is \(|\partial S|/(d|S|)=\Phi(S)\). A small conductance set is a bottleneck: a walk started uniformly inside it has a small one-step chance of escaping.
This interpretation explains why conductance is useful in the study of random walks and expansion. It identifies sets that are poorly connected to the rest of the graph relative to their degree volume. Conductance alone does not assert a particular mixing-time bound; it supplies a cut-based quantity that can be compared with spectral and probabilistic information.
Common mistake: treating a zero-volume set as a conductance candidate. In the triangle-with-isolated-vertex example, it is incorrect to calculate \(\Phi(\{z\})=|\partial\{z\}|/\operatorname{vol}(\{z\})=0/0=0\) and conclude that \(\Phi(G)=0\). The quotient \(0/0\) is undefined, and the set fails the required condition \(\operatorname{vol}(S)>0\). The correct minimum is over eligible positive-volume sets, each of which has ratio \(1\), so \(\Phi(G)=1\). When both sides of a cut have positive volume, one may use its smaller-volume side; one must not apply that observation to a zero-volume side.
Check Your Understanding
Use the definitions and verify that every set you test meets the relevant eligibility condition.
- For \(G=C_8\), with vertices \(1,\ldots,8\) and edges around the cycle in order, calculate \(\Phi(S)\) for \(S=\{1,2,3,4\}\).
- In a \(d\)-regular graph with \(d\ge1\), explain why the condition \(\operatorname{vol}(S)\le\operatorname{vol}(V(G))/2\) is equivalent to \(|S|\le |V(G)|/2\).
- For a cut whose two sides both have positive volume, explain why its smaller-volume side is eligible for the graph conductance minimum.
- Give a reason that the expression \(\Phi(S)\) is undefined when \(S\) consists only of isolated vertices.
- For the graph \(K_{3,3}\) in the worked example, calculate the conductance ratio when \(x=2\) and \(y=0\), showing the boundary size and volume separately.