Hypercube problem $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.
 A: 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.
A: 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.
