Let $H$ be the $n$-dimensional hypercube, i.e. $\{0,1\}^n$ with edges between two vertices if and only if they differ in exactly one co-ordinate. We say that an edge is in direction $i$ if its endpoints differ in exactly the $i$'th co-ordinate. Suppose $V$ is a subset of $H$ such that $|V| > 2^{n-1}$. Is it true that at least one connected component of the graph induced by $V$ contains edges in all $n$ direction? 



Connected components of large induced subgraphs of hypercubes
Yes, this is true. Thanks to Sukhada Fadnavis and Seva for pointing out in the comments that the argument I had written here was wrong. Instead I will point you to the paper where this is proved



> 
> ["Bulky subgraphs of the hypercube"](http://www.sciencedirect.com/science/article/pii/S0195669899903621), by Andrei Kotlov, Europ. J. Combinatorics (2000) **21**, 503-507
> 
> 
> 


As far as I can tell from looking at the literature, it is not known if there are configurations of more than $2^{n-1}$ vertices for which one can not find $n+1$ of them which induce a tree with an edge in every direction. This would be a strengthening of the result in question.


