It is known that the
[Cheeger constant](http://en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29)
of a
[hypercube graph](http://en.wikipedia.org/wiki/Hypercube_graph) $Q\_n$
is exactly $1$, regardless of its dimension $n$. Is $1$ also an upper bound
on the Cheeger constant of nontrivial induced connected subgraphs of $Q\_n$?


The Cheeger constant $h(G)$ is also known as the
[edge expansion](http://en.wikipedia.org/wiki/Expander_graph#Edge_expansion)
or the isoperimetic number.


To indirectly address a comment,
here are the Cheeger constants of more graphs:  

$h($[$Q\_n$](http://en.wikipedia.org/wiki/Hypercube_graph)$) = 1$   

$h($[$P\_n$](http://en.wikipedia.org/wiki/Path_graph)$) = 1 / \lfloor n / 2 \rfloor$   

$h($[$C\_n$](http://en.wikipedia.org/wiki/Cycle_graph)$) = 2 / \lfloor n / 2 \rfloor$   

$h($[$K\_n$](http://en.wikipedia.org/wiki/Complete_graph)$) = \lceil n / 2 \rceil$



Is the Cheeger constant of an induced subgraph of a cube at most 1?
Your conjecture is true, every subgraph of the cube has expansion constant at most $1$.


*Proof:* Suppose we are given a subgraph $G\subset Q\_n$, $n>1$ and cut the cube into $2$ $(n-1)$-dimensional subcubes $A\_1,A\_2$. (So that $A\_1\cup A\_2=Q\_n$) The key is to notice that each vertex in $A\_1$ is connected to one and only one vertex in $A\_2$. Then split $G$ into two parts, $G\_1=G\cap A\_1$ and $G\_2=G\cap A\_2$. One of these will have size $\leq \frac{|G|}{2}$, suppose it is $G\_1$. Because $G\_1$ is in $A\_1$, it is only connected to vertices in $A\_2$, and we have $\partial G\_1 \leq |G\_1|$. Since the expansion constant is the minimum, we conclude that $$h(G)\leq 1.$$ 


