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!