= Edit-distance stability for clique-free graphs
{title2=$e(G)\ge t_r(n)-k\Longrightarrow |E(G)\triangle E(H)|\le3k$}
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.
Back to article page
