The maximum number of 3-cycles in a graph with no cycles of length larger than 3?

Question

Suppose $G$ is a simple undirected graph with no cycles of length $\ge 4$. Some simple examples indicate that the number of 3-cycles $t$ may be less than $\displaystyle\left\lfloor \frac{|G|-1}{2} \right\rfloor$. Is this true? Why or why not?

Answer 1

This result is correct. This is an answer worked out by myself, which I think is beautiful.

Let $|G|=n$. Take out all 3-cycles in $G$, and those edges forms a new graph $G_T$. Now construct a graph $H$ as follows:

1. The vertices of $H$ are those of $G_T$ and $t$ new points, each corresponding to a 3-cycle.

2. $E(H)=\{uv:u \in V(G_T),v\text{ is the point corresponding to a 3-cycle that contains }u\}$.

It's easy to see that $\Vert H \Vert=3t$. Since $|G_T| \le n$, $|H| \le t+n$. $H$ doesn't contain any cycles, because if it contains one, the corresponding 3-cycles will form a cycle longer than 3 in $G_T$ (and also in $G$), a contradiction. Therefore $H$ is a forest, so $\Vert H \Vert \le |H|-1 \le t+n-1$. From here we deduce $3t \le t+n-1$, or, $\displaystyle t \le \left\lfloor \frac{n-1}{2} \right\rfloor$.