Lower bound on number of edges in "triangular" graph

Question I found in one of the previous year's exam:

Let $G$ a connected graph on $n \geq 3$ vertices, such that every edge participates in at least one triangle. Prove that $|E(G)| \geq \dfrac{3(n-1)}{2}$.

I tried proving using Turan's theorem on $\overline{G}$, but I get a less tight bound - $|E(G)| > \dfrac{3(n-2)}{4}$.

Using induction I'm getting nowhere as well; here it seems like I need to break the problem to $n$ odd and even, as it gives different number of edges. And even then, I don't know which edge/vertex to contract/delete.

Is it more straightforward than that?

Thanks in advance.

The assumption that $G$ is connected is crucial.

Otherwise, consider a graph of $6$ vertices which is composed of $2$ disjoint triangles.

Also, it is not true that $\overline{G}$ needs to be triangle free (all you need is an independent set of size $3$ in $G$).

A proof by induction actually works.

Base cases

$n=3,4$ are easily verified.

Induction step

Suppose we are given a graph $G$ with $n \ge 5$ vertices. Let $e = |E(G)|$.

Now if every vertex of $G$ had degree $\ge 3$, then we are done, as $2e \ge 3n$.

So assume there is a vertex $a$ of degree exactly $2$. (Why not $0$ or $1$?).

Let $b,c$ be the neighbours of $a$. Note that $\{b,c\}$ is an edge in $G$ (Why?)

Consider two cases:

Case 1) The edge $\{b,c\}$ is a part of a triangle other than $abc$.

In which case, we delete $a$ from $G$ to give a new graph $G'$ of $n-1$ vertices, satisfying the induction hypothesis.

Thus we get $e-2 \ge 3(n-2)/2$ and so $e \ge (3n - 2)/2 \gt 3(n-1)/2$ and so we are done.

Case 2) The edge $\{b,c\}$ is not part of any other triangle.

In this case, we delete the vertex $a$ and the edge $\{b,c\}$ to get a new graph $G'$.

Now it is possible that $G'$ is disconnected due to deletion of edge $\{b,c\}$. Since $G$ was connected, $G'$ has no more than two connected components, and we can try and apply the induction step to each connected component if each component has at least two vertices.

Thus if $n_1$ and $n_2$ (with $n_1 \ge 2$ and $n_2 \ge 2$) are the number of vertices in each connected component, we have that,

$e - 3 \ge 3(n_1 - 1)/2 + 3(n_2 -1)/2 = 3(n-3)/2$

Thus

$e \ge 3(n-1)/2$

and we are done.

If one of $n_1$, $n_2$ is $0$ or $1$, we can ignore that component and the above inequality still holds.

This post lacks the formalism necessary to constitute a formal proof (especially on an exam), but hopefully it gets you going in the right direction.

Suppose first that $n$ is odd. First, for terminology's sake, define $T_n$ to be the graph with $n$ vertices (we'll take $n$ odd) such that each edge participates in exactly one triangle. $T_3$ will be the standard triangle, and $T_n$ will in general, look like this:

It is not too hard to see that in the graph $T_n$, we have exactly $\frac{n-1}{2}$ triangles (this can be proved using an easy induction on odd $n$). Note that in such a graph, we have $$ |E| = 3 \cdot \# \text{triangles} = \frac{3(n-1)}{2}. $$

If $H$ is another "triangular" graph with $n$ vertices (still assuming $n$ is odd), then either $H$ is isomorphic to $T_n$, or $H$ has $T_n$ as a subgraph. This should establish the bound $|E| \geq \frac{3(n-1)}{2}$ for when $n$ is odd.

When $n$ is even, the same ideas should work, except we work not with the graph $T_n$, but rather with $T_n$ plus one vertex and plus two edges. We can call this new graph, say, $Z_n$:

Note that the number of triangles in $Z_n$ is now $\frac{n}{2} = \left\lceil \frac{n-1}{2} \right\rceil$, and hence the number of edges is then:

$$ 5 + \frac{3((n-3)-1)}{2}, $$ where we count first the 5 edges in the four vertices on the left, and then the remaining $n-3$ vertices as we did in the odd case. This gives that the total number of edges is then

$$ |E| \geq 5 + \frac{3(n-4)}{12} = \frac{3n -2}{2} = \left\lceil \frac{3(n-1)}{2} \right\rceil. $$

I apologize again for the lack of precision here, but hopefully this helps.