Erdős Problem #1079

Let \(r\geq 4\). If \(G\) is a graph on \(n\) vertices with at least \(\mathrm{ex}(n;K_r)\) edges then must \(G\) contain a vertex with degree \(d\gg_r n\) whose neighbourhood contains at least \(\mathrm{ex}(d;K_{r-1})\) edges? As Erdős [Er75] says 'if true this would be a nice generalisation of Turán's theorem'. This is true (unless \(G\) it itself the Turán graph), and was proved by Bollobás and Thomason [BoTh81]. Bondy [Bo83b] showed that if \(G\) has \(>\mathrm{ex}(n;K_r)\) edges then the corresponding vertex can be chosen to be of maximum degree in \(G\). The number of edges in the neighbourhood of \(v\) is the number of edges of \(G\) both of whose endpoints are adjacent to \(v\). Graphs on a single vertex are excluded, since there every degree is \(0\).