# Is the Cheeger constant of an induced subgraph of a cube at most 1?

It is known that the Cheeger constant of a 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 or the isoperimetic number.

To indirectly address a comment, here are the Cheeger constants of more graphs:
$h($$Q_n$$) = 1$
$h($$P_n$$) = 1 / \lfloor n / 2 \rfloor$
$h($$C_n$$) = 2 / \lfloor n / 2 \rfloor$
$h($$K_n$$) = \lceil n / 2 \rceil$

-
Isn't the Cheeger constant of a subgraph always smaller than or equal to the Cheeger constant of a graph? –  Seva Feb 7 '12 at 8:39
@Seva: Consider two copies of the complete graph connected at a single vertex. –  Eric Naslund Feb 7 '12 at 15:02
On this occasion: are the Cheeger constants of the discrete tori $C_n^r$ known? –  Seva Feb 8 '12 at 17:58

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.$$