The Erdős-Gyárfás conjecture states that every finite simple 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).
This is distinct from the Erdős-Gyárfás balanced coloring conjecture.
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.
Carr (2026a, p. 3) proved that every finite simple graph of graph diameter 2 and minimum vertex degree at least 3 contains a graph cycle of length 4 or 8.
For a minimal counterexample, chosen with smallest graph order and then smallest edge
count, Carr (2026b, pp. 3-4) proved that at least 
of its vertices have vertex degree 3. Ducoffe and Dumitru (2026) improved
this proportion to more than two thirds. 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 graph
order at most 40, all bipartite graphs of
graph order at most 66, and all cubic
graphs of graph order at most 48.
