A Stability Theorem for Maximal $K_{r+1}$-free Graphs

Abstract

For $r\ge 2$, we show that every maximal $K_{r+1}$-free graph $G$ on $n$ vertices with $(1-\frac{1}{r})\frac{n^2}{2}-o(n^{\frac{r+1}{r}})$ edges contains a complete $r$-partite subgraph on $(1-o(1))n$ vertices. We also show that this is best possible. This result answers a question of Tyomkyn and Uzzell.

21 pages