  Erd\H{o}s and Rothschild asked to estimate the maximum number, denoted by
H(N,C), such that every N-vertex graph with at least CN^2 edges, each of which
is contained in at least one triangle, must contain an edge that is in at least
H(N,C) triangles. In particular, Erd\H{o}s asked in 1987 to determine whether
for every C>0 there is \epsilon >0 such that H(N,C) > N^\epsilon, for all
sufficiently large N. We prove that H(N,C) = N^{O(1/log log N)} for every fixed
C < 1/4. This gives a negative answer to the question of Erd\H{o}s, and is best
possible in terms of the range for C, as it is known that every N-vertex graph
with more than (N^2)/4 edges contains an edge that is in at least N/6
triangles.
