= Edge-triangle symmetrization
For each real $c$, some maximizer of $e(G)-c k_3(G)$ among <graphs> on $n$ <vertices> is <complete multipartite graph>. Among maximizers maximize $\sum_v d(v)^2$. Cloning either of two nonadjacent <vertices> preserves the objective, since maximality forces their local contributions $d(v)-c e(G[N(v)])$ to agree. If their <vertex neighbourhoods> differ, the sum of the two changes in the squared-<degree of a vertex> objective is twice the size of their symmetric difference, a contradiction. Nonadjacency therefore partitions the <vertices> into classes with identical <vertex neighbourhoods>.
Back to article page
