Regularity survives sufficiently small changes of vertices and cross-edges

Choose $\delta >0$ so small that $2\delta <{ϵ}^{\mathrm{\prime }}-ϵ$, $\delta <1\mathrm{/}2$, and $20\delta \mathrm{/}{ϵ}^2<{ϵ}^{\mathrm{\prime }}-ϵ$.

Suppose, for contradiction, that $A^{\mathrm{\prime }}\subseteq X^{\mathrm{\prime }}$ and $B^{\mathrm{\prime }}\subseteq Y^{\mathrm{\prime }}$ witness failure of ${ϵ}^{\mathrm{\prime }}$-regularity. Put $A=A^{\mathrm{\prime }}\cap X$ and $B=B^{\mathrm{\prime }}\cap Y$. The vertex-change bounds and step 1.1 give $\mathrm{\mid }A\mathrm{\mid }\ge ϵ\mathrm{\mid }X\mathrm{\mid }$ and $\mathrm{\mid }B\mathrm{\mid }\ge ϵ\mathrm{\mid }Y\mathrm{\mid }$.

Removing the added vertices and accounting for the changed incidences changes either the witness density or the full-pair density by at most $10\delta \mathrm{/}{ϵ}^2$; this follows by dividing at most the affected rows, columns, and $\delta \mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }$ changed incidences by the lower bounds $\mathrm{\mid }{A}^{\mathrm{\prime }}\mathrm{\mid }\mathrm{\mid }{B}^{\mathrm{\prime }}\mathrm{\mid }\ge {ϵ}^2(1-\delta {)}^2\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }$.

Hence $\mathrm{\mid }d(A,B)-d(X,Y)\mathrm{\mid }>{ϵ}^{\mathrm{\prime }}-20\delta \mathrm{/}{ϵ}^2>ϵ$, contradicting [L1].

The contradiction proves that every sufficiently small edit, in particular the chosen $\delta$, leaves the pair ${ϵ}^{\mathrm{\prime }}$-regular.