Context: http://www.sciencedirect.com/science/article/pii/S0019995882904776
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:
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.
