 Solution

For disjoint nonempty vertex sets $U,V$, write $d(U,V)=e(U,V)/(|U||V|)$. A regular pair of vertex sets is $\epsilon$-regular if every $U^{\prime }\subseteq U,V^{\prime }\subseteq V$ with $|U^{\prime }|\ge \epsilon |U|$, $|V^{\prime }|\ge \epsilon |V|$ satisfies $|d(U^{\prime },V^{\prime })-d(U,V)|\le \epsilon$.

The Szemerédi regularity lemma states that, for every $\epsilon >0$ and integer $m_0$, there are $M,n_0$ such that every finite simple graph on $n\ge n_0$ vertices has a set partitionwith $m_0\le m\le M$, $|V_0|\le \epsilon n$, $|V_1|=\cdots =|V_m|$, and at most $\epsilon m^2$ irregular unordered pairs among the nonexceptional classes. Prove it for $0<\epsilon \le 1/2$; larger parameters follow by using a smaller one.

For the energy-increment proof of Szemerédi regularity, keep every exceptional vertex as a singleton cell in the set partition used to measure regularity energy. Define the equitable regularity energyThe sum is ordered, and on diagonal cells subset density means the average of the adjacency indicator, with zero on loops. Thus $0\le q\le 1$. If $U,V$ are refined into $U_a,V_b$, expanding squares givesThe cross term vanishes because the weighted arithmetic mean of the refined subset densities is the original subset density. Consequently every refinement of a set partition increases or preserves regularity energy.

Suppose the current nonexceptional classes have common size $t$ and there are $k$ of them. For each irregular pair $V_i,V_j$, choose witnesses $A_{ij},B_{ij}$ of sizes at least $\epsilon t$ and discrepancy greater than $\epsilon$. Refine each class by all its incident witness subsets. There are at most $k-1$ cuts in each class and at most $2^k$ resulting atoms. The witness rectangle is a union of refined rectangles. By the Cauchy-Schwarz inequality, its contribution to the variance identity is at leastIndeed, the sum of squared deviations on the witness rectangle is at least its total weight times the square of their weighted arithmetic mean. If more than $\epsilon k^2$ unordered pairs are irregular, summing even just one orientation of each givesprovided the exceptional set has at most $n/2$ vertices. This is the strictly positive regularity energy increment.

Restore equal class sizes without losing that increment. Divide every witness atom into blocks of size $\ell =\lfloor t/4^k\rfloor$ and make every leftover vertex an exceptional singleton. This is a further refinement of a set partition, so it cannot decrease $q$. There are at most $k{2}^k$ atoms, hence fewer than $k{2}^k\ell \le n{2}^{-k}$ newly exceptional vertices. If $t\ge 2\cdot 4^k$, then $\ell \ge t/(2\cdot 4^k)$, so the number of full blocks is at most $2k{4}^k$. Each original class produces at least one full block: its leftovers occupy less than $2^k\ell$, whereas $t\ge 4^k\ell >2^k\ell$. Thus the new class count is at least $k$.

Choose $R_{\ast }=\lceil 4{\epsilon }^{-5}\rceil +1$, and choose an initial integer $k_0\ge m_0$ large enough that $R_{\ast }{2}^{-k_0}\le \epsilon /2$. Initially partition into $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Take $n_0$ large enough that this initial exception is at most $\epsilon n/2$. During at most $R_{\ast }$ rounds, the additional exception is at most $R_{\ast }n{2}^{-k_0}\le \epsilon n/2$, so it never exceeds $\epsilon n\le n/2$.

A bound on class counts is obtained by iterating $k\mapsto 2k{4}^k$ at most $R_{\ast }$ times starting at $k_0$; call the resulting bound $M$. Increasing $n_0$ further to satisfy $n_0\ge 4M{4}^M$ guarantees $t\ge n/(2k)\ge 2\cdot 4^k$ at every round, so all full-block constructions are valid. If the desired regularity had not been reached after $R_{\ast }$ refinements, the regularity energy increments would total more than one, impossible. Therefore the process terminates with the required partition and bounds. The singleton treatment of discarded vertices is what preserves regularity energy monotonicity during equalization.