Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 17G / iv / Solution

If the edge $uv$ lies in no triangle, no vertex can be adjacent to both endpoints; hence the 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, every edge would run between these two parts, so $G$ would be bipartite andcontrary 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\ge 2$ 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\ge 3$, if every edge lies in a triangle, part (iii) givesOtherwise choose an edge $uv$ lying in no triangle and put $s=d(u)+d(v)\le 2n$. Deleting $u,v$ removes $s-1$ edges, so the graph $G^{\prime }=G-u-v$ hasIf $s=2n$, induction gives at least $n-1$ triangles in $G^{\prime }$, while the nonindependence proved above supplies a further triangle through $u$ or $v$.

If $s\le 2n-1$, then $e(G^{\prime })\ge (n-1{)}^2+2$. Induction first supplies a triangle $\Delta$ in $G^{\prime }$. 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$.