MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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


share|cite|improve this question

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

share|cite|improve this answer

Let $G'=(V',E')$ be a counterexample with $|V'|+|E'|$ 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'$. If $\delta_0 < \delta_1$, then deleting any edge of $G_1$ does not change the minimum degree of $G'$. Thus, by choice of $G'$, we have $\delta_0=\delta_1$. By minimality, we have that $|V(G_0)| \geq 2^{\delta_0}$ and that $|V(G_1)| \geq 2^{\delta_1}$. Therefore, $|V(G')| \geq 2^{\delta_0+1}$. But $\delta \leq \delta_0+1$, which contradicts that $G'$ is a counterexample.

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.