Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / A / 4 / b

In the standard regularity-partition convention, the vertex sets form a disjoint partition, the nonexceptional sets $V_1,\dots ,V_k$ are nonempty and have a common size, $|V_0|<ϵ|V(G)|$, and at most $ϵk^2$ unordered nonexceptional pairs fail to be $ϵ$-uniform. One can instead use weak inequality for the exceptional-set bound without affecting the argument below once the size bound is strict. The exceptional set absorbs the rounding remainder when the graph order is not divisible by $k$.