Answers are grounded in this paper and cite their sources.
Turán's Theorem says that an extremal Kr+1-free graph is r-partite. The Stability Theorem of Erdős and Simonovits shows that if a Kr+1-free graph with n vertices has close to the maximal tr(n) edges, then it is close to being r-partite. In this paper we determine exactly the Kr+1-free graphs with at least m edges that are farthest from being r-partite, for any m≥tr(n)−δrn2. This extends work by Erdős, Győri and Simonovits, and proves a conjecture of Balogh, Clemen, Lavrov, Lidický and Pfender.
No takes yet. Share an insight, caveat, or question.
Korándi et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: