mantel theorem bipartite graphs, two triangles share an edge Question:
I need to prove that if a graph is s.t $|E(G)|=\frac {n^2}4 +1 $ then it contains 2 triangles that share an edge. n is even.
My thoughts:
Mantel's theorem gives me that I ought to have one triangle. I was thinking about taking out the last edge $e$, so now I don't have a triangle, I can also figure now that this graph is bipartite. If I bring back the last edge it would indeed create a triangle. Does it suffice to say that since $\frac {n^2}4 +1 $ is the upper bound for this triangle-free graph then $G-e$ must be the complete bipartite graph of size $\frac n2$ and therefore $\forall x,z \in V(A)$ (one side of the graph) $: deg(x)=\frac n2$ ? And this will imply that since from x every possible edge is coming out to B (other side of graph) then adding $e=(b_1,b_2)$ between 2 nodes of B (w.l.o.g) will create two triangles - one formed by $x,b_1,b_2$, and another formed by $z,b_1,b_2$. 
Is this proof correct?
 A: We use induction on $n$ to prove that a graph with at least $\lfloor{\frac{n^2}4+1} \rfloor$ edges contains $K_4-e$.
For $n\leq 3$ the statement is true because it is void, for $n=4$ it is true by inspection.
Assume $n>4$ and the statement proven for smaller graphs.
Case 1: $n$ is even. Let the number of edges be $\frac{n^2}4+k$ ($k\geq 1)$.
The average degree is $\frac{2e}n=\frac n2+\frac{2k}n$.
If $k=1$ or $k=2$ then $\frac{2k}n<1$, so we can find a vertex with degree at most $\frac n2$.
Remove this vertex from $G$ to get a graph $G'$ with $n-1$ vertices
and at least $\frac{n^2}4+k-\frac n2=\frac{(n-1)^2}4+(k-\frac14)\geq\frac{(n-1)^2}4+\frac34
=\lfloor{\frac{(n-1)^2}4+1} \rfloor$ edges
(the last equality because $(n-1)^2\equiv 1\pmod 4$).
If $k>2$ then we can find a vertex with degree at most $\frac n2+\frac{2k}n$.
Remove this vertex from $G$ to get a graph $G'$ with $n-1$ vertices
and at least $\frac{n^2}4+k-\frac n2-\frac{2k}n=\frac{(n-1)^2}4+1+(k-\frac{2k}n-\frac54)$.
Since $k-\frac{2k}n=k(1-\frac 2n)\geq 3(1-\frac24)\geq\frac54$ the last quantity is positive.
So in both cases we can apply the induction hypothesis and find a $K_4-e$ in $G'$.
Case 2: $n$ is odd, say $n=2t+1$.
Let the number of edges be $\lfloor{\frac{n^2}4+k}=t^2+t+k \rfloor$ ($k\geq1$).
Again, by removing a vertex of minimum degree we find a graph $G'$
with at least $(t^2+t+k)(\frac{2t}{2t+1})$ edges.
It is sufficient to show that this value is at least $t^2+1$.
Simplifying the inequality you get $t^2+t(2k-1)-1\geq0$.
This parabola in $t$ has its minimum value at $t=k-\frac12$
and this value is $\frac34(2k-1)^2-1$, which is certainly positive when $k>1$.
For $k=1$ we get the inequality $t^2+t-1\geq 0$
and this is positive since $n>4$, so $t\geq2$.
