All vaults

Erdős problem 64

Erdős-Gyárfás: cycles of length a power of two

Does every finite graph in which every vertex has degree at least 3 contain a cycle whose length is a power of 2, such as 4, 8 or 16? Erdős and Gyárfás expected the answer to be no, so one finite counterexample would settle it.

Erdős's prize: $1,000 (history)Open on erdosproblems.com