A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi, who could prove this is true for $\delta>1/16$, and could further prove it for $\delta>0$ if we replace $K_5$ with $K_4$.

They further observed that it fails for $\delta =1/4$ if we replace $K_5$ with $K_7$: by a construction of Erdős and Rogers [ErRo62] (see [620]) there exists some constant $c>0$ such that, for all large $n$, there is a graph on $n$ vertices which contains no $K_4$ and every set of at least $n^{1-c}$ vertices contains a triangle. If we take two vertex disjoint copies of this graph and add all edges between the two copies then this yields a graph on $2n$ vertices with $\geq n^2$ edges, which contains no $K_7$, yet every set of at least $2n^{1-c}$ vertices contains a triangle.


See also [579] and the entry in the graphs problem collection.

View the LaTeX source