Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.
- When $n$ is even and $\Delta$ is even (so $\Delta \leq n-2$), we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,n/2-1\}$.
For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:
- When $n$ is even and $\Delta$ is odd, we pick a set of distances comprising $(\Delta-1)/2$ distances in $\{1,2,\ldots,n/2-1\}$ and $n/2$.
For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:
- When $n$ is odd and $\Delta$ is even we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,(n-1)/2\}$.
For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:
Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:
We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).
We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.
For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:
This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).
This is the contrapositive of the triangle removal lemma, which states that
For every $\alpha>0$, there is $\delta>0$ such that if $n$ is large enough and a graph on $n$ vertices has at most $\delta n^3$ triangles, then it is possible to make the graph triangle-free by removing at most $\alpha n^2$ edges.
Usually this is proved using the regularity lemma. In particular, your suggested approach won't work, since (for many values of $\alpha$) there are graphs which are $\alpha n^2$-far from triangle-free but still have fewer than $\frac{n^2}{4}$ edges. For example, take a complete graph on about $2\alpha n$ vertices (this has about $2\alpha n^2$ edges, half of which need to be removed to make the graph triangle-free) and make all other vertices isolated. If it did work, the dependency $\delta = \frac{\alpha}{6}$ would be much stronger than known results, which suggests that it can't be easily fixed.
Best Answer
Lemma. If $G$ has $n$ vertices, $m$ edges, and $t$ triangles, and $F$ is a forest on the same vertex set (edge-disjoint from $G$, without loss of generality), then $F \cup G$ has at most $t + 3m$ triangles.
Proof. There are, of course, $t$ triangles with all three edges in $G$.
There are at most $m$ triangles with one edge from $G$ and two edges from $F$. That's because for every edge $uv \in E(G)$, $F$ has at most one $u,v$-path of length $2$: it has at most one $u,v$-path of any length!
Finally, there are fewer than $2m$ triangles with two edges from $G$ and one edge from $F$. To see this, let $v$ be any vertex; there are fewer than $\deg_G(v)$ edges of $F$ in $N_G(v)$, so there are fewer than $\deg_G(v)$ triangles with two edges from $G$ incident to $v$, and one edge of $F$. Sum over all vertices $v$, and we get less than $2m$. $\square$
By induction with this lemma, we see that the union of $\alpha$ forests has at most $3 \binom{\alpha}{2}(n-1) = O(\alpha^2 n)$ triangles.
Asymptotically, this is matched by the union of $\alpha$ stars centered at $\alpha$ different vertices, which has $\binom \alpha 3 + \binom \alpha 2 (n-\alpha) = \Omega(\alpha^2 n)$ triangles.