Exact stability for Turán’s Theorem

Mantel’s Theorem and Turán’s Theorem are among the most classical results in extremal graph theory. Mantel’s Theorem, proven in 1907 and so perhaps the oldest result in extremal graph theory, asserts that the maximum number of edges of an $n$-vertex graph that does not contain the complete graph of order three is at most $\lfloor n^2/4\rfloor$. This bound is the best possible as witnessed by the complete bipartite graph with parts consisting of $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$ vertices. In 1941, Turán generalized this statement to graphs not containing the complete graph of order $r+1$: the maximum number of edges of an $n$-vertex graph that does not contain $K_{r+1}$ is attained by the complete $r$-partite graph with parts whose sizes differ by at most one, and this graph is the unique $n$-vertex graph with this number of edges that does not contain $K_{r+1}$. For general graphs $G$, the maximum number of edges of an $n$-vertex graph not containing $G$ is $\left(\frac{\chi(G)-2}{\chi(G)-1}+o(1)\right)\binom{n}{2}$, as shown by Erdős and Stone, and Erdős and Simonovits.

Let $t_r(n)$ be the maximum number of edges of an $n$-vertex graph that does not contain $K_{r+1}$. As the complete $r$-partite $n$-vertex graph with parts whose sizes differ by at most one is the unique $n$-vertex graph with $t_r(n)$ edges not containing $K_{r+1}$, it is natural to ask about the structure of $n$-vertex graphs not containing $K_{r+1}$ with the number of edges close to $t_r(n)$: do such graphs need to be $r$-partite, and if not, how close must they be to an $r$-partite graph? An exact answer to the first part of the question is known from the early 1980s: every $n$-vertex graph that does not contain $K_{r+1}$ and has at least $t_r(n)-\lfloor n/r\rfloor+2$ edges is $r$-partite. In the case of $r=2$, Erdős, Győri and Simonovits showed in the early 1990s that among all $n$-vertex graphs with $m\ge t_2(n)-n^2/20$ edges that do not contain $K_3$, the graph farthest from being bipartite (in terms of maximizing the number of edges needed to be removed to make it bipartite) is a suitable blow up of the cycle of length five. This paper generalizes this result to all values of $r$: there exists $\delta_r>0$ such that among all $n$-vertex graphs with $m\ge t_r(n)-\delta_r n^2$ edges that do not contain $K_{r+1}$, the graph farthest from being $r$-partite can be obtained by replacing two parts of the complete $r$-partite graph with a blow up of the cycle of length five.