I got the following question during a Discrete Mathematics exam. I have absolutely no clue how to even start solving and I just wanted to share it since it looks like an interesting problem, perhaps someone is able to provide a nice proof :).
Let $G = (V,E)$ be a graph, such that $|V| = n$ and $|E| = \left\lfloor{\dfrac{n^2}{4}}\right\rfloor + 1$. Show that there are at least $\left\lfloor{\dfrac{n}{2}}\right\rfloor$ triangles in $G$.
A proof of Mantel theorem, which states that if $G$ is triangle-free then $|E|\leq \lfloor\frac{n^2}{4}\rfloor$, proceeds by induction on $n$: we pick up an edge $xy$, we consider $G'=G-x-y$ and we use the inductive step on $G'$ plus the observation that $d(x)+d(y)\leq n$ to conclude. I try to modify slightly this idea to make it work for our new problem.
Note that the bound in Mantel's theorem is sharp: if $G$ has strictly more than $\lfloor\frac{n^2}{4}\rfloor$ edges it must contain a triangle. I'll use this fact in the proof.
Proof:
We prove that if $|E|\geq\lfloor\frac{n^2}{4}\rfloor+1$ then $G$ contains at least $\lfloor\frac{n}{2}\rfloor$ triangles (the $\geq$ sign makes it easier)
Base Step:
For $n=1$ and $n=2$ the claim clearly holds.
Inductive Step:
Let $n\geq3$ and $|E|\geq\lfloor\frac{n^2}{4}\rfloor+1$.
We might assume that $G$ is connected: if not, add an edge between disconnected components until the graph becomes connected; this way the number of edges increases (so $|E|\geq\lfloor\frac{n^2}{4}\rfloor+1$ still holds) and no triangles are created.
By Mantel's theorem we now that $G$ must contain at least one triangle since $|E|>\lfloor\frac{n^2}{4}\rfloor$; that is, the set $A=\{xy\in E(G): xy\quad\text{is contained in a triangle}\}$ is non-empty.
Now suppose that every edge of the graph is contained in some triangle. Then the number of triangles in $G$ is at least $|E|/3$ (since every triangle has three edges). $$|E|/3\geq\frac{1}{3}\left(\left\lfloor\frac{n^2}{4}\right\rfloor+1\right)\geq\frac{n^2}{12}$$ Note that $\frac{n^2}{12}\geq\frac{n}{2}$ for $n\geq 6$; also, for $n=3,4,5$ it shouldn't be difficult to check that the above inequality implies that the number of triangles is at least $\lfloor\frac{n}{2}\rfloor$. Hence the claim holds.
Hence, suppose that there is at least one edge which is not contained in any triangle, that is the set $B=\{xy\in E(G): xy\quad\text{is not contained in a triangle}\}$ is non-empty.
Now $E=A\cup B$ and $G$ is connected; hence, there must exist two edges in $A$ and $B$ respectively which are adjacent, ie $xy,yz\in E$ such that $xy$ is not contained in any triangle and $yz$ is contained in some triangle.
Since $xy$ is not contained in any triangle the neighbourhoods of $x$ and $y$ do not intersect, hence $d(x)+d(y)\leq n$. Consider $G'=G-x-y$; note that by removing $y$ we are destroying a triangle, we will use this at the end. Now: $$|E(G')|=|E(G)|-(d(x)+d(y)-1)\geq \left\lfloor\frac{n^2}{4}\right\rfloor+1-(n-1)=\left\lfloor\frac{(n-2)^2}{4}\right\rfloor+1$$ Hence by inductive hypothesis $G'$ contains at least $\lfloor\frac{n-2}{2}\rfloor=\lfloor\frac{n}{2}\rfloor-1$ triangles.
Consider now $G$. $G$ contains all the triangles in $G'$ and also the triangle which contains the edge $yz$. Hence $G$ contains at least $\lfloor\frac{n}{2}\rfloor$ triangles.