# Inequality involving size of nodes & min degree of graph

Lemma 1 on 3rd page.

Question excerpted / rewritten as follows:

Let $G=(V,E)$ be the $n$-dimensional hypercube. That is $V=\{0,1\}^n$ and $x$ and $y$ are adjacent if and only if they differ in exactly one coordinate. Let $H=(V',E')$ be a subgraph of $G$ and suppose that $d$ is the minimum degree of $H$. Prove that $|V'| \geq 2^d$.

Thanks!

$G$ above corresponds to an $n$-dimensional hypercube, so $G'=(V',E')$ is necessarily a subgraph of the hypercube. Let $v$ be any vertex in $V'$ (and hence also in $V$). Note that in a hypercube the number of vertices a distance $D$ in the $\ell^1$ norm from $v_0$ has exactly $D$ edges which lead to vertices a distance $D-1$ from $v$ and $n - D$ vertices a distance $D+1$ from $v$. Since $v \in V'$, at least $d$ vertices at distance $1$ from $v$ must be in $V'$. At distance 2 there are $d(d-1)$ incoming edges, but each site has only $2$ edges which connect to sites a distance $1$ from $v$, and hence there must be at least $d(d-1)/2 = \binom{d}{2}$ vertices a distance 2 from $v$. Now assume there are at least $\binom{d}{D}$ vertices in $V'$ that are a distance $D$ from $v$. Then there are $\binom{d}{D}(d-D)$ edges connecting these vertices to vertices $D+1$ from $v$. However each of these has at most $D+1$ edges connecting to vertices $D$ from $v$, and hence there is at least $\binom{d}{D}\frac{d-D}{D+1} = \binom{d}{D+1}$ vertices at distance $D+1$. Thus, by induction, there are at least $\sum_{D=0}^{d} \binom{d}{D} = 2^d$ vertices in $V'$.

A trivial example to show this bound is tight is to take a hypercube of dimension $d$ on the boundary of the original hypercube, as this has exactly $2^d$ vertices and has degree $d$ for all vertices.

I think the "official" reference for this fact is Section 4 of the following paper of Chung, Furedi, Graham, and Seymour:

http://www.math.ucsd.edu/~ronspubs/88_06_induced_cube.pdf

• It looks like they prove something slightly stronger in fact. Namely $|V'| \geq 2^d$' where $d$ is the average degree of $G$. – Tony Huynh Oct 8 '11 at 5:32

Let $G'=(V',E')$ be a counterexample with $|V'|$ minimum and then with the dimension of the hypercube in which $G'$ lives minimum. Let $G_0$ and $G_1$ be the subgraphs of $G'$ induced by the vertices of $G'$ with first component $0$ and $1$ respectively. Note that neither $G_0$ nor $G_1$ is empty, else $G'$ sits in a hypercube of lower dimension.

Now let $\delta_0$ and $\delta_1$ be the minimum degrees of $G_0$ and $G_1$ respectively, and let $\delta$ be the minimum degree of $G'$. Note that both $\delta_0$ and $\delta_1$ are at least $\delta-1$. By minimality, we have that $|V(G_0)| \geq 2^{\delta_0} \geq 2^{\delta-1}$ and that $|V(G_1)| \geq 2^{\delta_1} \geq 2^{\delta-1}$. Therefore, $|V(G')| \geq 2^{\delta}$, which contradicts that $G'$ is a counterexample.

• Do we really need that $\delta_0=\delta_1$ [I did not ubderstand the proof if this in the case when the minimal degree vertuces in $G_0$ have edges to $G_1$]? It looks that it suffices to use that both of them are at least $\delta-1$. – Fedor Petrov Aug 15 '17 at 17:54
• @FedorPetrov Yes, it looks like you are right. I simplified the argument as suggested. Thanks! – Tony Huynh Aug 15 '17 at 18:25