Turلnʹs Theorem and Maximal Degrees

Extending results of Bollobás and Thomason (1981,J. Combin. Theory Ser. B31, 111–114) and Bondy (1983,J. Combin. Theory Ser. B34, 109–111), we characterize graphs of ordernand size at leasttr(n) that do not have a vertexxof maximal degreedxwhose neighbours span at leasttr−1(dx)+1 edges. Furthermore, we show that, for every graphGof ordernand size at leasttr(n), the degree-greedy algorithm used by Bondy (1983,J. Combin. Theory Ser. B34, 109–111) and Bollobás and Thomason (1985,Ann. Discr. Math.28, 47–97) constructs a complete graphKr+1, unlessGis the Turán graphTr(n).