# Szemeredi's Regularity Lemma

Theorem: (SRL) For every $\epsilon>0$ and integer $m\geq 1$ there is an $M$ such that every graph $G$, with $|G|\geq m$ has an $\epsilon$-regular partition $V(G)=V_0\cup\ldots\cup V_k$ for some $m\leq k\leq M$.

Can someone explain to me why this statement is not trivial? For instance, what stops me choosing $M$ larger than $|G|$ and picking $k=|G|$, so I can split $G$ up into singletons, which is trivally $\epsilon$-regular for any $\epsilon>0$.

-
Order of quantifiers. –  Boris Bukh Nov 28 '09 at 11:17
@Boris: oops, our responses crossed –  Yemon Choi Nov 28 '09 at 11:20