Papex

Open problem · Mathematics · since 1995 · Open

Erdős–Gyárfás conjecture

Does every graph in which each vertex has at least three neighbours contain a cycle whose length is a power of two?

Summary

Paul Erdős and András Gyárfás made the conjecture in 1995, and Erdős offered US$100 for a proof and US$50 for a counterexample. Computer searches show that any counterexample must have at least 17 vertices, and any cubic counterexample at least 30.

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 18 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics