DISPROVED
This has been solved in the negative.
Let $Q_n$ be the $n$-dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that, for every $\epsilon>0$, if $n$ is sufficiently large, every subgraph of $Q_n$ with\[\geq \epsilon n2^{n-1}\]many edges contains a $C_6$?
In
[Er91] Erdős further suggests that perhaps, for every $k\geq 3$, there are constants $c$ and $a_k<1$ such that every subgraph with at least $cn^{a_k}2^n$ many edges contains a $C_{2k}$, where $a_k\to 0$ as $k\to \infty$.
The answer to this problem is no: Chung
[Ch92] and Brouwer, Dejter, and Thomassen
[BDT93] constructed an edge-partition of $Q_n$ into four subgraphs, each containing no $C_6$.
See also
[86].
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 #666, https://www.erdosproblems.com/666, accessed 2026-01-16
