For $e$ an edge, denote by $d(e)$ the number of triangles which contain $e$ as one of their sides. The critical observation is that, for a triangle formed by the edges $e,f,g$, we have the inequality $d(e)+d(f)+d(g)\leq 3k$. This observation is simple to prove, since if the sum exceeds $3k+1$, by Pigeonhole Principle we have a vertex which is not a vertex of the triangle, but it has been counted for two of the edges; this means it forms triangle with two of the edges of the initial triangle, and thus forms a $K_4$ with it, contradicting the hypothesis. Denote by $t$ and $m$ the number of triangles and edges respectively. Summing up the previous relation after all the triangles, we obtain the inequality $\sum_{\triangle}{[d(e)+d(f)+d(g)]}\leq 3kt$. In this sum, each $d(e)$ is added when the edge $e$ is part of a triangle, which happens exactly $d(e)$ times; thus the sum is in fact equal to $\sum_{\text{edges}}{d(e)^2}$. By Cauchy-Schwarz we get: $3kt\geq \sum_{\text{edges}}{d(e)^2}\geq \frac{(\sum_{\text{edges}}{d(e)})^2}{m}=\frac{9t^2}{m}$, since each triangle is counted three times and three times exactly in the sum. By Turan's Theorem, we know that $m\leq 3k^2$, thus we obtain $t\leq k^3$, and we claim this is the desired result. Indeed, it is a simple construction of the example; since we have equality in Turan's Theorem, we can easily think about the graph $K_{t,t,t}$, that is, the tripartite graph with an equal number of vertices in each group. A triangle is formed by picking a vertex from each group, so trivially $t=k^3$.

Induct on k to prove that there are $k^3$ triangles. Base case is trivial. Given a graph with $3(k+1)=3k+3$, select a triangle $ABC$ and denote $S$ the set of the other $3k$ vertices. Let $P=\{A,B,C\}$. In $P$ there is exactly $1$ triangle, while in $S$ there are (at most) $k^3$ triangles. Now count triangles with one vertex in $S$ and two in $P$. Since for each $X\in S$ the three segments $XA,$ $XB,$ $XC$ cannot be simultaneously edges in $G$ -- for a $K_4$ will thus be created -- at most one triangle with vertex $X$ exists, hence at most $3k$ triangles falls under this case. Finally, count triangles with one vertex in $P$ and two in $S$. Choose two vertices from $S$, say $X$ and $Y$, which are connected in $G$. That is to say that $XY$ is an edge, and by Turan there are (at most) $3k^2$ edges in $S$. Now only one of $AXY$, $BXY$, $CXY$ can be a triangle of $G$, for two of them create a $K_4$ -- recall that $A$, $B$, $C$ are connected, as $ABC$ is a triangle. Hence at most $3k^2$ of his type exist. Since $1+3k+3k^2+k^3=(k+1)^3$ and the tripartite graph $K_{k,k,k}$ provides us with a model, we are done.