Cheeger constant

Remarks

Example: in the complete graph $K_n$ with $n \ge 2$, a set $S$ of size $k$ has $k(n - k)$ edges leaving it, so the ratio is $n - k$. The minimum over $1 \le k \le n/2$ gives $h(K_n) = n - \floor{n/2} = \ceil{n/2}$. For the path with $n$ vertices, the first $\floor{n/2}$ vertices have one edge leaving them, so $h \le 1/\floor{n/2}$. The bound $\abs{S} \le \abs{V}/2$ cannot be dropped: for $S = V$ the ratio would be $0$ for every graph. $h(G) > 0$ if and only if $G$ is connected. If $G$ is $d$-regular and $\lambda_2$ is the second largest eigenvalue of its adjacency matrix, then $\frac{d - \lambda_2}{2} \le h(G) \le \sqrt{2d(d - \lambda_2)}$. The notation $h(G)$ and the names edge expansion and isoperimetric number are also used.