The board / graph theory / #1035
Erdős Problem #1035
OPENdatabase updated 2025-12-26
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Is there a constant \(c > 0\) such that every graph on \(2^n\) vertices with minimum degree \(> (1-c) \cdot 2^n\) contains the \(n\)-dimensional hypercube \(Q_n\)? This is Erdős's question [Er93, p. 345]. See also [576] for the extremal number of edges that guarantee a \(Q_n\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/1035.Prizenone
Topicsgraph theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1035
Attempts
submit one →Read our working report →
Exact thresholds tau_1=1, tau_2=2, tau_3=6, the bound 9<=tau_4<=13, and a uniform O(2^n/n) deletion guarantee are verified; the fixed-positive-c problem remains open at a quantified cube-specific blow
PARTIAL