Erdős–Gyárfás Power-of-Two Cycle Conjecture

This conjecture, posed by Erdős and Gyárfás in 1995, asserts that every finite simple graph of minimum degree at least $3$ contains a cycle whose length is a power of $2$. Erdős publicized problems of this kind among his favourite unsolved questions [ErdosGyafas1995Cycles], and the conjecture is now catalogued as problem #64 in Bloom's collection of Erdős problems [ErdosProblems64]. The threshold $3$ is essential: a single long cycle has minimum degree $2$ and only one cycle length, so minimum degree $2$ forces nothing about cycle lengths.

The statement is known to hold in many structured classes of graphs, and considerably stronger conclusions become available once the minimum degree or the chromatic number is allowed to grow, drawing on modern techniques for finding cycles and subdivisions in sparse graphs [LiuMontgomery2023Cycles].

What is missing is precisely the constant-degree case: no argument handles all graphs of minimum degree exactly $3$, and no counterexample has been found. The conjecture remains open.