= Solution
If the edge $uv$ lies in no triangle, no vertex can be adjacent to both endpoints; hence the <vertex neighbourhood>[neighbourhoods] satisfy $\Gamma(u)\cap\Gamma(v)=\varnothing$.
Suppose $|\Gamma(u)|+|\Gamma(v)|=2n$. The two disjoint neighbourhoods then partition $V(G)$. If both were <independent set>[independent], every edge would run between these two parts, so $G$ would be <bipartite graph>[bipartite] and
$$
e(G)\leq|\Gamma(u)|\,|\Gamma(v)|
\leq\left(\frac{|\Gamma(u)|+|\Gamma(v)|}{2}\right)^2=n^2,
$$
contrary to $e(G)=n^2+1$. Thus at least one neighbourhood contains an edge, and that edge forms a triangle with $u$ or $v$.
We now prove by induction on $n\geq2$ the <Triangle lower bound one edge above the Mantel threshold>: every graph on $2n$ vertices with at least $n^2+1$ edges has at least $n$ triangles. Part (ii) is the base case. For $n\geq3$, if every edge lies in a triangle, part (iii) gives
$$
t(G)\geq\frac{n^2+1}{3}\geq n.
$$
Otherwise choose an edge $uv$ lying in no triangle and put $s=d(u)+d(v)\leq2n$. Deleting $u,v$ removes $s-1$ edges, so the graph $G'=G-u-v$ has
$$
e(G')=n^2+2-s\geq(n-1)^2+1.
$$
If $s=2n$, induction gives at least $n-1$ triangles in $G'$, while the nonindependence proved above supplies a further triangle through $u$ or $v$.
If $s\leq2n-1$, then $e(G')\geq(n-1)^2+2$. Induction first supplies a triangle $\Delta$ in $G'$. Delete one edge of $\Delta$; the remaining graph still has at least $(n-1)^2+1$ edges, so induction supplies $n-1$ triangles avoiding that edge. Together with $\Delta$, these give at least $n$ distinct triangles in $G$.
Back to article page
