The Erdős–Gyárfás Conjecture
Every graph in which every vertex has at least three neighbours contains a cycle whose length is a power of two.
Disputed
A candidate resolution of the roughly thirty-year-old conjecture, produced with foundation-model assistance, is circulating and being checked. It is recorded here as disputed pending independent verification — a headline claim is not a proof.
Formal statement
Obstruction
Why the direct approaches fail
Erdős attached a $100 prize. The conjecture is known for graphs of large girth, for K₃,₃-free and for planar graphs, and there exist graphs of minimum degree three with remarkably few power-of-two cycles — which is exactly what makes both a proof and a counterexample delicate. Cycle-length spectra are notoriously hard to control; forcing a length in a sparse target set like {4, 8, 16, …} while only bounding minimum degree has been the sticking point for thirty years.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Verify or refute the circulated candidate resolution against the known near-extremal families.
- 02Determine the minimal degree threshold above which a power-of-two cycle is forced unconditionally.
- 03Sharpen the girth-based results toward minimum degree three via dependent random choice.
- 04Analyse whether the cycle-length spectrum of a cubic expander must intersect {2^k}.
Erdős–Gyárfás has its own lane in the solver, running continuously alongside every other problem.