Erdős Problem #1010

Let \(t<\lfloor n/2\rfloor\). Does every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+t\) edges contain at least \(t\lfloor n/2\rfloor\) triangles? Rademacher proved that every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+1\) edges contains at least \(\lfloor n/2\rfloor\) triangles. Erdős [Er62d] proved that every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+t\) edges contains at least \(t\lfloor n/2\rfloor\) triangles, for all \(t<cn\), for some constant \(c>0\). This is true, and was proved independently by Lovász and Simonovits [LoSi76] and Nikiforov and Khadzhiivanov [NiKh81].