Turán’s theorem inverted

In this note we complete an investigation started by Erdős in 1963 that aims to find the strongest possible conclusion from the hypothesis of Turán’s theorem in extremal graph theory.Let Kr+(s1,…,sr) be the complete rr-partite graph with parts of sizes s1≥2,s2,…,srs1≥2,s2,…,sr with an edge added to the first part. Letting tr(n)tr(n) be the number of edges of the rr-partite Turán graph of order nn, we prove that:For all r≥2r≥2 and all sufficiently small c>0c>0, every graph of sufficiently large order nn with tr(n)+1tr(n)+1 edges contains a Kr+(⌊clnn⌋,…,⌊clnn⌋,⌈n1−c⌉).We also give a corresponding stability theorem and two supporting results of wider scope.