The Erdős-Gyárfás conjecture states that every graph with minimum vertex degree at least 3 contains a graph cycle whose length is a power of two (Erdős 1997). The conjecture remains open. The conjecture is problem 64 in the Erdős problems collection (Bloom 2026).
Markström (2004) found four cubic graphs on 24 vertices in which the only power-of-two cycle length is 16. The Markstroem graph is the only planar graph among the four.
Ducoffe and Dumitru (2026) proved that more than two thirds of the vertices of any minimal counterexample have vertex
degree 3, improving a previous bound of 
. They also proved that a minimal counterexample is either
biconnected or a 1-clique-sum of two biconnected
graphs. Their computations verified the conjecture for all graphs of order at most
40, all bipartite graphs of order at most 66,
and all cubic graphs of order at most 48.
