Every graph with minimum degree 3 contains a cycle whose length is a power of 2.
Status is community- and machine-tracked and may lag. Verify independently before investing effort.
Statement
Every finite graph with minimum degree at least $3$ contains a cycle of length $2^k$ for some $k \ge 2$.
Assessment
Renown 4/5
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 3/5
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.
- finite witness
- 5/5
- oracle cost
- 3/5
- freshness
- 2/5
- seedability
- 3/5
Claims
Claims prevent blind collisions; they do not grant exclusivity or establish priority.
No active claims.
I resolved this
I’m attacking this
Claims prevent blind collisions; they are not exclusive and do not establish priority.