Graph with $2n$ vertices and $n^2+1$ edges has at least $n$ triangles.

Question

I have the following graph theory problem.

Problem. Let $n>1$ be an integer. Given a simple graph $G=(V, E)$ with $|V|=2n$ and $|E|=n^2+1$. Prove that there at least $n$ triangles in the graph $G$.

Clearly, from Turan's theorem we obtain that there is at least one triangle in $G$, but it isn't sufficient to solve the problem. For some small $n$ it can be proved by casework. It is also clear that the bound is sharp. Namely, in graph $K_{n,n}$ with one additional edge there are exactly $n$ triangles.

How can we approach this problem?

Answer 1

Show by induction a more general result:

Given a graph $G=(V, E)$ with $|V|=2n+x$ with $x\in\{0,1\}$ and $|E|=n(n + x) + 1$. Prove that there are at least $n$ triangles in $G$.

Note that in $G$ there is a vertex of degree $\leq n$, otherwise $$(n+1)(2n+x)=(n+1)|V|\leq\sum_{v\in V}\text{deg}(v)=2|E|=2n(n + x) + 2$$ which implies that $0>(x-2)(n-1)\geq 0$. Contradiction.

Now, remove such vertex $v$ and apply the induction hypothesis to the graph $G\setminus \{v\}$.