Szemerédi's regularity lemma (statement)

Lemma. For every $\varepsilon>0$ there exists $M(\varepsilon)$ such that every graph $G$ on $n\ge1$ vertices admits a partition into $k\le M$ parts, each of size within $\varepsilon n$ of each other, such that all but $\varepsilon k^2$ pairs of parts are $\varepsilon$-regular.

Application. Proves Szemerédi's theorem (long arithmetic progressions), triangle removal lemma, Roth's theorem.

Conclusion. The regularity lemma is a powerful structural tool in combinatorics.