Let $P_{ 10}$ be a path on $10$ vertices. A graph is said to be $P_{ 10}$-free if it does not contain $P_{ 10}$ as an induced subgraph. The well-known Erd\H{ o}s-Gy\'{ a}rf\'{ a}s Conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of $2$. In this paper, we show that every $P_{ 10}$-free graph with minimum degree at least three contains a cycle of length $4$ or $8$. This implies that the conjecture is true for $P_{ 10}$-free graphs.
Categories: math.CO