Problem 1035

../

---

Statement. 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$?

Status. Open.

Source. erdosproblems.com/1035, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1035, https://www.erdosproblems.com/1035.

References.

• [Er93] Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350. Chapter V, problem 10, printed pp. 345--346: "Is it true that there is a fixed $\epsilon>0$ so that every graph of $2^n$ vertices every vertex of which has degree $>(1-\epsilon)2^n$ contains the $n$-dimensional cube $C^{(n)}$", the problem's question (the survey's $C^{(n)}$ is $Q_n$), followed by two fallback problems should it fail: I, the smallest $m>2^n$ for which minimum degree $>(1-\epsilon)2^n$ (or $(1-\epsilon)m$) on $m$ vertices forces $C^{(n)}$; II, the $u_n$ for which minimum degree $>2^n-u_n$ on $2^n$ vertices forces the cube (printed "$C^{(m)}$" on p. 346). Stated without proof or reference. Library home: erdos_1993_my_favorite_solved_unsolved_problems_graph_theory.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• erdos_1993_my_favorite_solved_unsolved_problems_graph_theory