 Dense regular pair from edge surplus

The Szemerédi regularity lemma gives equal cells. If every regular cross-cell pair had density at most $1/4$, their total edge contribution would be at most $n^2/8$. Exceptional vertices, within-cell edges and irregular pairs contribute at most $(2\eta +1/(2m_0))n^2$. Choosing $\eta =1/100$ and $m_0=100$ contradicts $e(G)=n^2/6$. The dense pair is $1/8$-regular since it is already $\eta$-regular.