{"data":{"id":"erdos-gyarfas-1995","statement_oneline":"Every graph with minimum degree 3 contains a cycle whose length is a power of 2.","statement_full_latex":"Every finite graph with minimum degree at least $3$ contains a cycle of length $2^k$ for some $k \\ge 2$.","source":{"title":"Erdős-Gyárfás conjecture (Erdős prize problem)","arxiv":null,"url":"https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gy%C3%A1rf%C3%A1s_conjecture","year":1995,"area":"math.CO"},"renown":{"score":4,"rationale":"Carries an Erdős cash prize; the name alone draws attention. Proved for several classes (e.g. cubic planar); expert opinion on its truth is genuinely divided, unusual for a famous conjecture."},"attackability":{"score":3,"rationale":"Finite witness (a cubic-ish graph avoiding all power-of-two cycle lengths); the oracle (cycle-length spectrum) is exponential in principle but feasible to roughly 40 vertices; high-girth cubic graphs and cages are natural seeds since girth 5 kills C4 for free.","subscores":{"finite_witness":5,"oracle_cost":3,"freshness":2,"seedability":3}},"status":"open","last_verified_open":"2026-07-23","added":"2026-07-24","effective_status":"open","claims":[],"status_events":[{"id":"seed-erdos-gyarfas-1995","conjecture_id":"erdos-gyarfas-1995","status":"open","date":"2026-07-24T00:00:00.000Z","note":"Loaded from seed data."}],"resolutions":[]},"notice":"Status is community- and machine-tracked and may lag. Verify independently before investing effort."}