Problem Statement
Let $G$ be a graph with chromatic number $\aleph_1$. Must there exist an edge $e$ such that, for all large $n$, $G$ contains a cycle of length $n$ containing $e$?
Categories:
Graph Theory Chromatic Number
Progress
A problem of Erdős, Hajnal, and Shelah [EHS74], who proved that $G$ must contain all sufficiently large cycles (see [594]).This is true, and was proved by Thomassen [Th83].
Source: erdosproblems.com/737 | Last verified: January 16, 2026