OPEN
This is open, and cannot be resolved with a finite computation.
Let $c>0$ and let $f_c(n)$ be the maximal $m$ such that every graph $G$ with $n$ vertices and at least $cn^2$ edges, where each edge is contained in at least one triangle, must contain a book of size $m$, that is, an edge shared by at least $m$ different triangles.
Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or $f_c(n)\gg \log n$?
A problem of Erdős and Rothschild. Alon and Trotter showed that, provided $c<1/4$, $f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that $f_c(n)\to \infty$.
Edwards (unpublished) and Khadziivanov and Nikiforov
[KhNi79] proved independently that $f_c(n) \geq n/6$ when $c>1/4$ (see
[905]).
Fox and Loh
[FoLo12] proved that\[f_c(n) \leq n^{O(1/\log\log n)}\]for all $c<1/4$, disproving the first conjecture of Erdős.
The best known lower bounds for $f_c(n)$ are those from Szemerédi's regularity lemma, and as such remain very poor.
See also
[600] and
the entry in the graphs problem collection.
View the LaTeX source
Additional thanks to: Zach Hunter
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 #80, https://www.erdosproblems.com/80, accessed 2026-01-16
