Expander graph

Remarks

The complete graph $K_4$ is a $2$-expander: a set $S$ of $1$ or $2$ vertices has $\abs{S}(4 - \abs{S})$ edges leaving it, so the ratio is $4 - \abs{S} \ge 2$. The cycles $C_n$ do not form a family of expanders: they are $2$-regular, and an arc $S$ of $\floor{n/2}$ consecutive vertices has $\abs{\partial S} = 2$, so $h(C_n) \le 2/\floor{n/2} \to 0$, and clause 2 fails. Families of expanders of every degree $d \ge 3$ exist. For example, for each $d \ge 3$ there is $\varepsilon > 0$ such that a random $d$-regular graph on $n$ vertices is an $\varepsilon$-expander with probability tending to $1$ as $n \to \infty$. An equivalent spectral form uses the second largest eigenvalue $\lambda_2$ of the adjacency matrix. The discrete Cheeger inequalities say $\frac{d - \lambda_2}{2} \le h(G) \le \sqrt{2d(d - \lambda_2)}$ for a $d$-regular graph $G$. So clause 2 holds if and only if the spectral gap $d - \lambda_2(G_n)$ is bounded away from $0$.