Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

$B$ is an n-dimensional hypercube, considered as undirected graph. Let $A$ be a subset of the vertices of $B$ such that $|A| \gt 2^{n-1}$.

Let $H$ is a subgraph of $B$ induced by $A$. Prove that $H$ has at least $n$ edges.

Any help, would be greatly appreciated.

share|cite|improve this question
Why does it seem like a Ramsey-theory-type problem? – Jan Dvorak Jan 17 '13 at 18:07
can you explain a bit more :(... – DiscreteMath'sFan Jan 17 '13 at 18:08
Basically, the original problem in Ramsey theory says that if you have a large enough complete graph and color its edges by $n$ colors, you are destined to find a single-colored complete subgraph of a given size in the graph, for every such size. Namely, every edge-2-colored $K_6$ contains a single-colored $K_3$ (triangle). – Jan Dvorak Jan 17 '13 at 18:14
I can't find a way how to solve the problem with this... – DiscreteMath'sFan Jan 17 '13 at 18:14
up vote 8 down vote accepted

Temporarily consider one of the $n$ coordinate axes. Your hypercube has $2^{n-1}$ edges parallel to that axis. Since $B$ has more than $2^{n-1}$ vertices, it must have two on the same one of those $2^{n-1}$ edges. So $H$ has an edge parallel to the coordinate axis under consideration. Apply this to all $n$ of the axes.

share|cite|improve this answer
+1 Nice answer! Looks like you wrote $B$ instead of $A$ above. – polkjh Jan 17 '13 at 18:21
thanks, I will try to solve it with it. If anyone has another ideas, please write them :) – DiscreteMath'sFan Jan 17 '13 at 18:23
there is simpler combinatoric solution Ill post tommorow (I can not post the solution now since this problem was homework for me and my fellow-students) – bteo Jan 21 '13 at 16:20

We can build n-dimensional hypercube using two $(n-1)$-dimensional hypercubes. This gives us the vertices set power $|Vn| = 2^{n}$ for the n-dimensional hypercube Gn(Vn, En). Knowing |Vn-1| and |En-1| for (n-1)-dimensional hypercube we know |En| for n-dimensional hypercube. |En| = 2*|En-1| + $2^{n-1}$.

Solving this recurrence relation gives us |En| for any dimension. |En| = $n*2^{n-1}$.

Then we choose at least $(2^{n-1}+1)$ vertices to be in the $A$ subset by choosing at most $(2^{n-1} - 1)$ vertices that wont be in $A$. We know that every vertex in $n$-dimensional hypercube is connected to $n$ edges (or less if we remove some vertices). So removing the maximum of $(2^{n-1} - 1)$ vertices removes no more than $r = (2^{n-1} - 1)*n$ edges. $r = (2^{n-1} - 1)*n = |En| - n$.

It appers that the induced graph H has at least |En| - r edges. |En| - r = |En| - (|En| - n) = n. We can conclude that H has at least n edges.

Sorry if there is something unclear. English is not my native language. I would be glad if someone improves my post. I've done my best to format it and make it readable but I am new to LaTeX and I preferred not to use it for now.

share|cite|improve this answer

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.