Odd-ordered Cayley graphs satisfy Erdős–Gyárfás

Abstract

Erdős and Gyárfás conjectured that every graph with minimum degree at least three contains a power-of-two-length cycle. We prove every Cayley graph of odd order satisfies the conjecture. As a corollary, we find that Cayley graphs of finite nilpotent groups satisfy the conjecture as well.