Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 3 / a / Solution

For disjoint nonempty vertex sets $X,Y$, their edge density of a bipartite graph isThe pair $(X,Y)$ is a $\epsilon$-regular pair ifwhenever $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$, $|X^{\prime }|\ge \epsilon |X|$, and $|Y^{\prime }|\ge \epsilon |Y|$. A partition $V_0,V_1,\dots ,V_m$ is equitable when $|V_1|=\cdots =|V_m|$; $V_0$ is its exceptional class.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and $m_0$ there are integers $M,n_0$ such that every graph on at least $n_0$ vertices has an equitable partitionwithfor which all but at most $\epsilon m^2$ pairs $(V_i,V_j)$, $1\le i<j\le m$, are $\epsilon$-regular.