Erdős–Gyárfás conjecture: does minimum degree 3 force a cycle of length a power of 2? (Erdős #64)
Statement
Does every finite graph with minimum degree at least $3$ contain a cycle of length $2^k$ for some $k\geq 2$? Here the minimum degree of a graph is the least number of edges at any vertex, and a cycle of length $\ell$ is a closed walk through $\ell$ distinct vertices. Only cycle lengths $4, 8, 16, 32, \ldots$ count. The finiteness hypothesis is essential: an infinite tree with all degrees $3$ has no cycles at all, so the question is trivially false for infinite graphs.
Acceptance. FULLY RESOLVES: (a) a counterexample — an explicit finite graph $G$ with minimum degree $\geq 3$, delivered in machine-readable form (e.g. graph6), together with machine-checkable certification that for EVERY $k\geq 2$ with $2^k\leq |V(G)|$ the graph contains no cycle of length exactly $2^k$ (per-length exhaustive check or SAT UNSAT certificates, with the checking code); or (b) a complete proof that every finite graph of minimum degree at least $3$ contains a cycle of length $2^k$ for some $k\geq 2$ — machine-checkable (Lean/Coq) preferred (a formal statement already exists in formal-conjectures), else a full written proof; it must cover the small-degree regime not handled by Liu–Montgomery. ADVANCES: a proof for a new natural graph family strictly beyond those stated in the background (e.g. all claw-free graphs, all planar graphs, all cubic graphs); an explicit and substantially reduced value of the minimum-degree constant in the Liu–Montgomery theorem, with proof; or an extension of the exhaustive search certifying that no counterexample exists among cubic (or min-degree-3) graphs beyond the vertex-count bound stated in the background, with reproducible generation + checking code and an exhaustiveness certificate. Deliver the witness graph + certificates, the proof file, or the search code + attained bound.
Background
The Erdős–Gyárfás conjecture, posed by Erdős and Gyárfás and appearing repeatedly in Erdős's late problem papers [Er93, p.343], [Er94b], [Er95, p.174], [Er96], [Er97b], [Er97c]; Erdős offered $1000 for a solution. Listed as open on erdosproblems.com/64 (fetched 2026-07-13, status 'falsifiable', tagged 'graph theory | cycles'). Erdős himself believed the answer should be NO, and conjectured more strongly that for every $r$ there is a graph of minimum degree at least $r$ with no cycle of length $2^k$ for any $k\geq 2$. That stronger conjecture is FALSE: Liu and Montgomery [LiMo20] proved that the answer is affirmative whenever the minimum degree exceeds some absolute constant, via a much stronger theorem — if the average degree of $G$ is sufficiently large, there is a large integer $\ell$ such that $G$ contains a cycle of every even length $m\in[(\log \ell)^8,\ell]$. So the surviving open case is small minimum degree, essentially minimum degree exactly $3$. The conjecture is known for several special families — e.g. planar claw-free graphs (Daniel–Shauger), 3-connected cubic planar graphs (Heckman–Krakovski), and recently $P_{13}$-free graphs (no induced 13-vertex path, arXiv:2410.22842) and graphs of diameter $2$ (arXiv:2508.19302) — and exhaustive computer search (Markström) found no counterexample among cubic graphs on fewer than 30 vertices. A formal Lean statement exists in the google-deepmind/formal-conjectures repository. The attacker's tools: SAT/ILP-driven search for a small counterexample (for a candidate graph on $n$ vertices only the finitely many lengths $2^k\le n$ need be excluded, each certifiable by an UNSAT certificate), exhaustive generation of cubic and min-degree-3 graphs past the verified range, or proof techniques extending Liu–Montgomery's method down to small degree.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #64 (T. F. Bloom) | website |
| REF-02 | Liu–Montgomery, A solution to Erdős and Hajnal's odd cycle problem (proves the large-degree case) | arxiv |
| REF-03 | Formalised statement (Lean, formal-conjectures) | website |
| REF-04 | #69 in Extremal Graph Theory (graphs problem collection) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.