Problem 64

Erdős Problem #64 [status: falsifiable; formalized: yes]. Does every finite graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k\geq 2$? Current best: Conjectured by Erd\H{o}s and Gy\'{a}rf\'{a}s, who believed the answer must be negative, and in fact for every $r$ there must be a graph of minimum degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$. Prize: $1000. Tags: cycles, graph theory.