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

Zoltán Füredi

Published 2015-01-13Version 1

The following sharpening of Tur\'an'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)\geq e(G)-t$. Using this result we present a concise, contemporary proof (i.e., one applying Szemer\'edi's regularity lemma) for the classical stability result of Simonovits.