OPEN
This is open, and cannot be resolved with a finite computation.
Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an edge contained in at least $r$ triangles. Let $r\geq 2$. Is it true that\[e(n,r+1)-e(n,r)\to \infty\]as $n\to \infty$? Is it true that\[\frac{e(n,r+1)}{e(n,r)}\to 1\]as $n\to \infty$?
Ruzsa and Szemerédi
[RuSz78] proved that $e(n,r)=o(n^2)$ for any fixed $r$.
See also
[80].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #600, https://www.erdosproblems.com/600, accessed 2026-02-13
