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.
 A: 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.
A: 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.
