OPEN
This is open, and cannot be resolved with a finite computation.
Is there a constant $c>0$ such that every graph on $2^n$ vertices with minimum degree $>(1-c)2^n$ contains the $n$-dimensional hypercube $Q_n$?
Erdős
[Er93] says 'if the conjecture is false, two related problems could be asked':
- Determine or estimate the smallest $m>2^n$ such that every graph on $m$ vertices with minimum degree $>(1-c)2^n$ contains a $Q_n$, and
- For which $u_n$ is it true that every graph on $2^n$ vertices with minimum degree $>2^n-u_n$ contains a $Q_n$.
See also
[576] for the extremal number of edges that guarantee a $Q_n$.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1035, https://www.erdosproblems.com/1035, accessed 2026-01-16
