Edit-distance stability for clique-free graphs ($e(G)\ge t_r(n)-k⟹|E(G)△E(H)|\le 3k$)

A clique-free graph near the Turan theorem edge bound is close to a complete multipartite graph. Choose a maximum-degree vertex, split its neighbourhood from the remaining vertices, and apply induction inside the neighbourhood. The degree bound implies that missing cross edges are at least twice the number of edges inside the remaining class. This inequality controls all three types of edits and gives the constant three.

Fix an odd cycle length. If the graph has edge density at least $1/2-ϵ$ and sufficiently few copies of that cycle, odd-cycle copies from positive triangle density forces few triangles in a graph. The triangle removal lemma deletes at most $ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, after which the clique-free edit bound applies with two parts. Absorbing its linear rounding error into the density margin gives the displayed bound for large order.