Given a connected graph $G$, the *Cheeger constant* $h(G)$ (a.k.a. *Cheeger number* or *isoperimetric number*) roughly measures the "bottleneckedness" of $G$. See [Wikipedia](https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)) for the precise definition.


I want to have an approximate value of the maximal Cheeger constant among all *trivalent* (or *$3$-regular*) graphs with a large fixed number of vertices, but couldn't find an answer by googling. The precise problem is:



> 
> **Question:** Let $\mathcal{T}\_n$ denote the set of all $3$-regular graphs with $n$ vertices. How does $h\_n:=\max\_{G\in\mathcal{T}\_n}h(G)$ behave asymptotically as $n\to+\infty$?
> 
> 
> 


Any comments are appreciated!



Reference request: maximal Cheeger constant for 3-regular graphs
This is expander territory and someone will doubtless give a reference soon.


Meanwhile, here's a simple proof that $\liminf h\_n \le 1$.


Consider a connected induced subgraph $H$ with $n\_1,n\_2,n\_3$ vertices of degree 1,2,3, respectively. Since $H$ is connected, we have $n\_1+2n\_2+3n\_3\ge 2(n\_1+n\_2+n\_3)-2$ (sharp for a tree); that is, $n\_3\ge n\_1-2$, say $n\_3=n\_1-2+\delta$. Also $|\partial H|\le 2n\_1+n\_2$, so in summary, the Cheeger constant is at most
$$ \frac{2n\_1+n\_2}{2n\_1+n\_2-2+\delta}, $$
which is bounded above by $1+o(1)$ as $H$ grows in size.


I think you need a good expander graph to get a lower bound.


Also see [this](https://mathoverflow.net/questions/209413/cheeger-numbers-for-3-regular-graphs?rq=1). 


**ADDED**: I just realised there is a much simpler way to show that $h\_n\le 1$ except for tiny $n$: Take $H$ to be a cycle.


