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

Kamil Popielarz, Julian Sahasrabudhe, Richard Snyder

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 s…