Context: http://www.sciencedirect.com/science/article/pii/S0019995882904776

Lemma 1 on 3rd page.

Question excerpted / rewritten as follows:

(V,E) = a graph on {0,1}^n, where there is an edge between x, x' iff (x,x') differ in exactly one coordinate. I.e., |V| = 2^n, |E| = 2^n * n /2.

mindegree(G'=(V',E')) = minimum degree of any vertex in G.

Given: V' is a subset V, E' is a subset of E; d = mindegree((V',E'))

Prove: |V'| >= 2^d

Thanks!

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!