= Solution
We prove <edit-distance stability for clique-free graphs> by induction on $r$, using the <symmetric difference> of <edge> sets as the distance. For $r=1$, a $K_2$-free <graph> is edgeless, and there is nothing to change. For $r\ge2$, choose a <vertex> of maximum degree $d$, let $A$ be its neighbourhood and put $B=V(G)\setminus A$. Then $G[A]$ is $K_r$-free. Write
$$
D=t_r(n)-e(G),\qquad D_A=t_{r-1}(d)-e(G[A]),\qquad b=e(G[B]),\qquad m=|A||B|-e_G(A,B).
$$
Both deficits are nonnegative by the <Turan theorem>. Since every <vertex> of $B$ has degree at most $d=|A|$,
$$
e_G(A,B)+2b\le |B|d,\qquad m\ge2b.
$$
The complete $r$-partite <graph> formed from an $(r-1)$-partite <Turan graph> on $A$ and the new class $B$ has at most $t_r(n)$ <edges>. Thus $L=t_r(n)-t_{r-1}(d)-|A||B|\ge0$, and direct subtraction gives
$$
D=L+D_A+m-b.
$$
By induction, edit $G[A]$ into a complete $(r-1)$-partite <graph> using at most $3D_A$ changes. Delete the $b$ <edges> inside $B$, and add the $m$ missing <edges> between $A$ and $B$. The resulting <graph> is complete $r$-partite on the same <vertex> set, and
$$
3D_A+b+m\le3D_A+3(m-b)+3L=3D\le3k,
$$
where the inequality uses $m\ge2b$. \b[The required edit distance is at most $3k$.] Empty partition classes are allowed; a sufficiently dense nondegenerate case has the usual full complement of classes.
For the odd-cycle conclusion, use two standard consequences of the <Szemerédi regularity lemma>, stated explicitly. The <triangle removal lemma> says that for every $\alpha>0$, some $\beta>0$ ensures that a <graph> with at most $\beta n^3$ <triangles in a graph> can be made triangle-free by deleting at most $\alpha\binom n2$ <edges>, for all sufficiently large $n$. Also, for each fixed odd length $\ell\ge3$ and each $\beta>0$, there is $\zeta>0$ such that a <graph> with at least $\beta n^3$ <triangles in a graph> contains at least $\zeta n^\ell$ copies of $C_\ell$.
For clarity, the latter <odd-cycle copies from positive triangle density> consequence follows by applying regularity with error small relative to $\beta$, removing exceptional, irregular and very sparse pairs, and retaining a <triangle in a graph> among the remaining regular dense pairs. The <graph embedding lemma for regular pairs> counts a positive constant times $n^\ell$ embeddings of any fixed <graph> properly three-coloured into those three clusters, including $C_\ell$. Dividing by the fixed number of descriptions of a cycle gives the same conclusion for unlabelled copies.
Apply <triangle in a graph> removal with $\alpha=\epsilon$, and take the resulting $\beta$. A $C_{2013}$-free <graph> cannot have $\beta n^3$ <triangles in a graph> for large $n$, by the preceding consequence. Delete at most $\epsilon\binom n2$ <edges> to obtain a triangle-free $G'$. With $N=\binom n2$,
$$
e(G')\ge(1/2-2\epsilon)N,\qquad t_2(n)-e(G')\le2\epsilon N+n/4.
$$
Apply the proved stability result with $r=2$. The resulting complete bipartite <graph> $H$ satisfies
$$
|E(G)\mathbin\triangle E(H)|\le\epsilon N+3(2\epsilon N+n/4)=7\epsilon N+3n/4.
$$
Choose $n_0(\epsilon)$ also large enough that $3n/4\le4\epsilon N$. \b[Then the distance is at most $11\epsilon\binom n2$.]
For the unheaded continuation, use the same $\beta$ and its associated $\zeta$, and set $\delta=\zeta/2$. Having at most $\delta n^{2013}$ cycles rules out $\beta n^3$ <triangles in a graph> just as before. The identical deletion and stability calculation applies. \b[A sufficiently small $\delta=\delta(\epsilon)>0$ gives the same $11\epsilon$ bound.]
Back to article page
