sagt aus, daß für ϵ > 0 und l ∈ ℕ zwei Zahlen L, n₀ ∈ ℕ so existieren, daß die Eckenmenge jedes Graphen G der Ordnung n ≥ n₀ eine Partition E(G) = E₀ ∪ E₁ ∪ E₂ ∪…∪ E_k besitzt, die folgende Bedingungen erfüllt:

Ein Paar nichtleerer disjunkter Eckenmengen (X, Y) in einem Graphen G heißt dabei ϵ-regulär, wenn \begin{eqnarray}|d(X,Y)-d({X}^{\prime},{Y}^{\prime})|\lt \varepsilon \end{eqnarray}

für alle Mengen X′ ⊆ X und Y′ ⊆ Y mit |X′ | ≥ ϵ|X| > 0 und |Y′ | ≥ ϵ|Y | > 0 gilt. Dabei ist \begin{eqnarray}d(X,Y)=\frac{k(X,Y)}{|X|\cdot |Y|},\end{eqnarray}

und k(X, Y) ist die Anzahl der Kanten in G mit einem Endpunkt in X und einem Endpunkt in Y.

E. Szemeredi bewies diese Aussage 1975. Das Regularitätslemma hat eine Reihe von Anwendungen in der extremalen Graphentheorie, und mit ihm wird oft die Existenz bestimmter Teilgraphen in Graphen nachgewiesen.