Turán's theorem and maximal degrees (Q1306430)

The main aim of the paper is to characterize graphs of order \(n\) and size \(t_r(n)+ a\geq t_r(n)\) that do not have a vertex \(x\) of maximal degree \(d_x\) whose neighbours span at least \(t_{r-1}(d_x)+ a+ 1\) edges. Here, as usual, \(t_r(n)\) is the number of edges in the Turán graph \(T_r(n)\), the uique \(r\)-partite graph of order \(n\) with maximal number of edges. The simple result proved in the paper is a substantial extension of Turán's classical theorem. Furthermore, it is shown that, for every graph \(G\) of order \(n\) and size at least \(t_r(n)\), the degree-greedy algorithm used by Bondy, Bollobás and Thomason constructs a complete graph \(K_{r+1}\), unless \(G\) is the Turán graph \(T_r(n)\). The results extend earlier results of Bollobás and Thomason, and Bondy.