= Solution
\b[Symmetrization for an arbitrary real coefficient.] Among <graphs> maximizing $f(G)=e(G)-c k_3(G)$, choose one maximizing
$$
Q(G)=\sum_{x\in V(G)}d(x)^2.
$$
For a <vertex> $x$, put $L(x)=d(x)-c e(G[N(x)])$. This is the contribution of <edges> and <triangles in a graph> containing $x$. If $u,v$ are nonadjacent, <Zykov symmetrization> replacing $u$ by a clone of $v$ changes $f$ by $L(v)-L(u)$; the opposite replacement changes it by $L(u)-L(v)$. Maximality implies $L(u)=L(v)$, so both changes preserve $f$.
Let $S=N(v)\setminus N(u)$ and $T=N(u)\setminus N(v)$. In the first replacement the <vertex degrees> in $S$ increase by one and those in $T$ decrease by one; in the opposite replacement these changes reverse. The changes to $d(u)^2+d(v)^2$ cancel when the two replacements are added. Since $(d+1)^2+(d-1)^2-2d^2=2$,
$$
\Delta_{u\gets v}Q+\Delta_{v\gets u}Q=2(|S|+|T|).
$$
If the two <vertex neighbourhoods> differ, one replacement increases $Q$, a contradiction. Thus every pair of nonadjacent <vertices> has the same <vertex neighbourhood>. Nonadjacency, with equality allowed, is an <equivalence relation>: if $u$ and $v$ are nonadjacent and $v$ and $w$ are nonadjacent, their identical <vertex neighbourhoods> forbid $uw$ as well. Its classes are <independent sets> and every cross-class <edge> is present. Therefore
$$
\boxed{\text{some maximizer of }e(G)-c k_3(G)\text{ is complete multipartite}.}
$$
This <edge-triangle symmetrization> works for either sign of $c$.
\b[The exact supporting line.] For $n\geq3$, write
$$
e_2=e(T_2(n)),\quad e_3=e(T_3(n)),\quad t_3=k_3(T_3(n)),\quad c_*=(e_3-e_2)/t_3.
$$
We prove the <triangle support line between bipartite and tripartite Turan graphs> by maximizing $e-c_*k_3$. First $c_*\geq2/n$. For $n=3,4,5$, its values are respectively $1,1/2,1/2$. For $n\geq6$, the exact balancing of the <Turán graph> gives $e_3\geq n^2/3-1/3$, while $e_2\leq n^2/4$ and the <arithmetic-geometric mean inequality> gives $t_3\leq n^3/27$. Hence
$$
n(e_3-e_2)-2t_3\geq\frac{n^3}{108}-\frac n3\geq0.
$$
By <edge-triangle symmetrization> a maximizing <graph> can be taken <complete multipartite graph>; among such maximizers use one with the fewest nonempty parts. If there are at least four parts, let $a,b$ be the two smallest sizes. Then $a+b\leq n/2$. Merging them loses $ab$ <edges> and $ab(n-a-b)$ <triangles in a graph>, so the objective changes by
$$
ab\{c_*(n-a-b)-1\}\geq0.
$$
This contradicts the choice of the number of parts. Thus at most three parts remain.
For three part sizes $a\geq b\geq d>0$, the objective is
$$
ad(1-c_*b)+b(a+d).
$$
If $1-c_*b\leq0$, merging the parts of sizes $a,d$ does not decrease it, again contradicting minimality. If $1-c_*b>0$ and $a-d\geq2$, transferring one <vertex> from the largest to the smallest part raises $ad$ by $a-d-1>0$ and strictly increases the objective. Thus a three-part maximizer has all sizes differing by at most one, and is $T_3(n)$. A maximizer with at most two parts has objective at most $e_2$, since it has no <triangles in a graph> and the <Mantel theorem> bounds its <edges>. Finally,
$$
e(T_3(n))-c_*k_3(T_3(n))=e_2.
$$
Therefore every <graph> satisfies $e(G)-c_*k_3(G)\leq e_2$. At the prescribed <edge> count this gives
$$
\boxed{k_3(G)\geq\theta k_3(T_3(n)).}
$$
For $n\leq2$, the conclusion is simply the nonnegative lower bound zero. All rounding in the <Turán graphs> has been retained.
\b[One edge above the bipartite threshold.] Write $n=2m$. We prove the <Triangle lower bound one edge above the Mantel threshold> by induction on $m\geq2$, allowing at least $m^2+1$ <edges>. For $m=2$, five <edges> on four <vertices> give two <triangles in a graph>, and adding <edges> preserves this bound.
We will also use the following consequence of an inductive bound: on $2a$ <vertices>, at least $a^2+q$ <edges>, for an integer $q\geq1$, force at least $a+q-1$ <triangles in a graph>. Delete surplus <edges> first to leave exactly $a^2+q$. Repeatedly delete an <edge> in a <triangle in a graph> until $a^2+1$ <edges> remain. The <Mantel theorem> guarantees such a <triangle in a graph> at every step; each deletion destroys at least one distinct <triangle in a graph>. Apply the inductive bound to the remaining <graph>.
Now take exactly $m^2+1$ <edges>. If every <edge> lies in a <triangle in a graph>, the <edge-triangle incidence bound> gives $3k_3(G)\geq m^2+1$. This is at least $3m$ for $m\geq3$; the base case was handled separately.
Otherwise choose an <edge> $uv$ in no <triangle in a graph>. Its endpoints have disjoint <vertex neighbourhoods>, so $d(u)+d(v)\leq2m$. Deleting $u,v$ removes exactly $d(u)+d(v)-1$ <edges> and leaves at least $(m-1)^2+1$ <edges>. If $d(u)+d(v)\leq2m-1$, it leaves at least $(m-1)^2+2$ <edges>, and the strengthened inductive bound gives at least $m$ <triangles in a graph> already.
If $d(u)+d(v)=2m$, induction gives at least $m-1$ <triangles in a graph> after deletion. There must be an additional <triangle in a graph> containing $u$ or $v$. Otherwise both $N(u)$ and $N(v)$ are <independent sets>; since they are disjoint and cover all <vertices>, $G$ would be <bipartite graph>, contradicting $e(G)>m^2$ by the <Mantel theorem>. Hence
$$
\boxed{k_3(G)\geq m=n/2.}
$$
The bound is sharp: add one internal <edge> to one class of the <complete bipartite graph> $K_{m,m}$. Its <triangles in a graph> are precisely that <edge> together with each of the $m$ <vertices> in the other class.
Back to article page
