Problem Statement
Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?
Categories:
Graph Theory Set Theory
Progress
A problem of Erdős and Hajnal. Folkman [Fo70] and Nešetřil and Rödl [NeRo75] have proved that for every $n\geq 1$ there is a graph $G$ which contains no $K_4$ and is not the union of $n$ triangle-free graphs.See also [582] and [596].
Source: erdosproblems.com/595 | Last verified: January 15, 2026