A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity

Abstract

The following sharpening of Turán's theorem is proved. Let $T_{n,p}$ denote the complete $p$--partite graph of order $n$ having the maximum number of edges. If $G$ is an $n$-vertex $K_{p+1}$-free graph with $e(T_{n,p})-t$ edges then there exists an (at most) $p$-chromatic subgraph $H_0$ such that $e(H_0)\ge e(G)-t$. Using this result we present a concise, contemporary proof (i.e., one applying Szemerédi's regularity lemma) for the classical stability result of Simonovits.

4 pages plus references

Cited by in corpus (4)

• The spectral radius of graphs with no intersecting odd cycles
• Ramsey goodness of books revisited
• New Short Proofs to Some Stability Theorems
• The typical structure of graphs with no large cliques