The desired finimum is $ f(n) = [\frac {3n-2}{2}]$ (*) where $ [...]$ denotes the integer part. In another words, we have $ f(2n) = 3n-1$ and $ f(2n+1)=3n$ for all $ n \geq 3$. A graph which staisfies the statement of the problem will be called "good" (even if it does not have the minimal number of edges). First, it is easy to see that if $ k=2n+1$ then we may consider the good graph whose vertices are $ A,B_1, \cdots, B_{2n}$ and edges are $ AB_i$ for all $ i$ and $ B_{2i-1}B_{2i}$ for $ i=1,\cdots , n$. Thus $ f(2n+1) \leq 3n$. For $ k=2n$, for some $ n \geq 2$, we may start from the above good graph with order $ 2n-1$, consider any of its edges, say $ AB$, and add the vertex $ X$ and edges $ XA$ and $ XB$, to obtain a good graph with order $ 2n$ and $ 3n-1$ egdes. Thus $ f(2n) \leq 3n-1$. Clearly, we have $ f(3)=3$ and $ f(4)=5$. Moreover, since a good graph is connected, each vertex has degree at leas $ 1$. And since each edge must belong to some triangle, each vertex has degree at least $ 2$. Note that a graph with $ n$ vertices and less than $ \frac{3n}2$ edges must have a vertex with degree no more than $ 2$. It follows that a good graph with $ n$ vertices and $ f(n)$ edges must have a vertex with degree $ 2$. Now, we prove the desired minimum by induction on $ n$. Assume that $ f(k)$ is given by (*) for all $ k \leq 2n$ for some $ n \geq 2$. Now consider a good graph $ G$ with $ 2n+1$ vertices and $ f(2n+1)$ edges. Let $ X$ be a vertex with degree $ 2$, and $ XAB$ a triangle in $ G$. Assume that $ f(2n+1) \leq 3n-1$. Delete $ X$ and the edges $ XA$ and $ XB$. This leaves a graph $ G'$ with $ 2n$ vertices and no more than $ 3n-3$ edges. Since $ f(2n) = 3n-1$, it means that $ G'$ is not good. But we only destroy one triangle from $ G$ and preserve the connectivity. Thus, that $ G'$ is not good comes from the fact that the edge $ AB$ does not belong to a triangle anymore. Since $ G'$ is connected and have at least three vertices, it means that $ A$ or $ B$ is connected by an edge to some other vertex, say $ AC$ is an edge. Then, draw edge $ BC$. The resulting graph $ G''$ is good, has $ 2n$ vertices and no more than $ 3n-2$ edges, contradicting that $ f(2n) = 3n-1$. Thus, $ f(2n+1) \geq 3n$, which gives $ f(2n+1)=3n$. Now, consider a good graph $ G$ with $ 2n+2$ vertices and $ f(2n+2)$ edges. Let $ X$ be a vertex with degree $ 2$, and $ XAB$ a triangle in $ G$. Assume that $ f(2n+2) \leq 3n+1$. Delete $ X$ and the edges $ XA$ and $ XB$. This leaves a graph $ G'$ with $ 2n+1$ vertices and no more than $ 3n-1$ edges. Since $ f(2n+1) = 3n$, it means that $ G'$ is not good. But we only destroy one triangle from $ G$ and preserve the connectivity. Thus, as above, that $ G'$ is not good comes from the fact that the edge $ AB$ does not belong to a triangle anymore. If $ A$ has degree $ 1$ in $ G'$, then delete $ A$ and the edge $ AB$. This leaves a good graph $ G''$ with $ 2n$ vertices and no more than $ 3n-2$ edges, contradicting that $ f(2n) = 3n-1$. Thus $ A$ has degree at least $ 2$ in $ G'$, and similarly $ B$ has degree at least $ 2$ in $ G'$. If we delete the edge $ AB$, we obtain a graph $ G'''$ with $ 2n$ vertices and no more than $ 3n-2$ edges. Using that $ f(2n)=3n-1$, we deduce that $ G'''$ cannot be good. But, in $ G'''$, each edge belongs to some triangle. Thus $ G'''$ is not connected. Since we have deleted only one edge from a connected graph, it means that $ G'''$ has exactly two connected components, with respective order $ a$ and $ b$. Note that each of these components is a good graph. Thus $ 3n-2 \geq f(a)+f(b)$ with $ a+b = 2n+1$. It follows that $ a$ and $ b$ have opposite parities, say $ a=2x$ and $ b=2y+1$. Then $ x+y = n$ and, using the induction hypothesis, $ 3n-2 \geq f(a) +f(b) = 3x-1+3y = 3n-1$, a contradiction. Therefore $ f(2n+2) \geq 3n+2$, and we are done. Pierre.

Since $G$ is a connected graph,$G$ admits a spanning tree on $n$ vertices,name it $T$.Then $T$ has $n-1$ edges.Now, $\forall e \in T$ must be contained in at least one triangle.So $|E(G)|\ge |E(T)|+|E(G-T)| \ge |E(T)|+[\frac{n}{2}]=(n-1)+[\frac{n}{2}]= [\frac{3n-2}{2}] $.An example is the windmill graph.

The answer is $n - 1 + \lceil\frac{n-1}{2}\rceil$. For the construction, consider a path of length $n-1$ (so it goes through $n$ vertices), then for each vertex an even distance away from the start, connect it with the vertex a distance $2$ from it. Keep doing this until we get to the end. Assume $G$ had minimal edges. Let $T$ be a spanning tree of $G$, so $T$ has $n-1$ edges. Now, we add in the rest of the edges of $G$ in a way such that every edge connects the endpoints of a cherry. Let $S$ be the set of edges not in a triangle yet, originally $S$ is size $n-1$. Observe that each time we add in an edge, we remove at most $2$ elements from $S$: If we remove more than $2$, then there must be a cycle with that edge as a chord, however this means one of the edges in that cycle was not in $T$, so it must be the endpoints of a cherry. This creates another cycle, so one of those edges must not be in $T$, so it must be the endpoints of a cherry, which creates another cycle. This process must terminate, which means that there is a cycle in $T$, contradiction. Furthermore, we can always choose edges that are on the endpoints of a cherry. If there was not, and assume $S$ was nonempty (or else we'll be done), consider an edge $e\in S$. $e$ has to be part of a cherry (otherwise it's not connected), but if over all cherries containing $e$, non of the edges joining the endpoints were part of $G$, then for $e$ to be part of a triangle, we need $e$ to be the endpoints of another cherry (which can't be added in yet otherwise it contradicts our earlier claim). This means an extra $2$ edges, however we can remove those two edges from $G$ and add in the edge joining the endpoints of a cherry containing $e$, for a new minimal, a contradiction. Thus, such an edge must exist. Now, since every time we add an edge, we remove at most $2$ edges from $S$, we need to add at least $\lceil\frac{n-1}{2}\rceil$ edges, for a total of $m = n-1 + \lceil\frac{n-1}{2}\rceil$

Let $T$ be the spanning tree of $G$. We know that it has $n-1$ vertices. It's clear that the number of triangles in $G$ is at least $\lfloor \frac{n}{2}\rfloor$. However, when we add an edge to the spanning tree, a unique cycle is formed. Since there are at least $\lfloor \frac{n}{2}\rfloor$ unique cycles, the number of edges added needs to be at least $\lfloor \frac{n}{2}\rfloor$. Therefore, $m\ge n-1+\lfloor \frac{n}{2}\rfloor$. If $n$ is odd, take the friendship graph on $n$ vertices. If $n$ is even, take the friendship graph on $n-1$ vertices and add in a vertex at the top connected to two vertices in the same "clover".

We claim the answer is $\left\lceil{\frac{3}{2}(n-1)}\right\rceil$. For odd $n$, take the friendship graph on $n$ vertices. For even $n$, take the friendship graph on $n-1$ vertices, and the remaining vertex connected to endpoints of an edge in the friendship graph. We proceed by strong induction on $n$ with the base case trivial. Assume the statement for $n=3,4,\ldots,k$. Let $G$ be a graph on $k+1$ vertices such that each edge is contained in at least one triangle. Note that every vertex is contained in at least one triangle. Clearly there must not exist a vertex of degree $1$. Assume there exists a vertex $v$ of degree $2$ (otherwise every vertex has degree at least $3$ so we are done). Let the neighbors of $v$ be $u_1$ and $u_2$. The key is to look at $G\setminus v$. In $G\setminus v$, the only edge which can be not contained in a triangle is $u_1u_2$. Assume this edge is not contained in a triangle (otherwise $|E(G)\setminus v|\geq\left\lceil\frac{3}{2}(k-1)\right\rceil$ so $|E(G)|\geq \left\lceil\frac{3}{2}(k-1)\right\rceil+2\geq\left\lceil\frac{3}{2}((k+1)-1)\right\rceil$). There are two cases. Case 1: $k+1$ is odd. Among $u_1$ and $u_2$, there exists a vertex connected to another vertex distinct from $u_1$ and $u_2$. Assume WLOG $u_2$ is connected to $w\neq u_1$. Adding an edge between $u_1$ and $w$ creates a triangle containing $u_1u_2$. Now all edges in $G\setminus v\cup u_1w$ are contained in at least one triangle, so by the induction hypothesis, $|E(G\setminus v)\cup u_1w|\geq\frac{3}{2}k-1$. Thus, \begin{align*} |E(G)|&\geq\frac{3}{2}k-2+2\\ &=\left\lceil\frac{3}{2}((k+1)-1)\right\rceil. \end{align*} Case 2: $k+1$ is even. $G\setminus v\setminus u_1u_2$ has at most $2$ connected components and every edge is contained in at least one triangle. If $G\setminus v\setminus u_1u_2$ is connected, it has at least $\frac{3}{2}k-\frac{3}{2}$ edges so \begin{align*} |E(G)|&\geq\frac{3}{2}k-\frac{3}{2}+3\\ &=\frac{3}{2}(k+1)\\ &>\left\lceil\frac{3}{2}((k+1)-1)\right\rceil. \end{align*}If $G\setminus v\setminus u_1u_2$ is not connected, it has two connected components $G_1$ and $G_2$. Since $|V(G_1)|+|V(G_2)|=k$ is odd, if follows that $|V(G_1)|$ and $|V(G_2)|$ have different parity so $|E(G\setminus v\setminus u_1u_2)|\geq \frac{3}{2}k-\frac{3}{2}-1=\frac{3}{2}k-\frac{5}{2}$. Thus, \begin{align*} |E(G)|&\geq\frac{3}{2}k-\frac{5}{2}+3\\ &=\left\lceil\frac{3}{2}((k+1)-1)\right\rceil. \end{align*}Thus the induction step is proved. $\square$

Just take a spanning tree! Let $E_1$ be the set of all edges which are not in a triangle. We start with a spanning tree $T$ of $G$ with $n-1$ edges and imagine adding edges to the graph and thus deleting edges from $E_1$. Claim. Each new edge deletes at most two edges from $E_1$. Proof. Clear as $T$ has no cycles. $\blacksquare$ Thus we need at least $\lceil 1/2(n-1) \rceil$ edges to be added, hence the bound. For construction, take the $n-1$-star and connect outer vertices alternately.

We claim the answer is $m=n-1+\lceil \tfrac{n-1}{2} \rceil$. In order to prove this, realize that since $G$ is a connected graph, which implies it has a spanning tree. Now, consider a spanning tree of $G$ which has $n-1$ edges. None of these edges form a triangle since trees have no cycle. Now, suppose we add edges in until each edge is contained in at least one triangle. Note that if we add an edge in it forms at least one triangle because there is no cycle, and we can delete the triangle and only consider the rest of the edges while adding in edges. However each move deletes at most two edges that were originally in the graph. So it will take at least $\lceil \tfrac{n-1}{2} \rceil$ moves. Note that if on each move we take a leaf and if there is another leaf with the same stem, we connect those to make a triangle, and if there is not another leaf with the same stem, make a triangle with the edges connecting the end of the leaf and the stem of the leaf, and the stem of the leaf and the stem of the stem of the leaf. Then delete the triangle, then if $n-1$ is even we can finish this process in $\tfrac{n-1}{2}$ moves, and if $n-1$ is odd we can take $\tfrac{n-2}{2}$ moves and then we will have one edge left consider "undeleting" one of the triangles we built that has a vertex on this edge, then we can add one more edge to make a triangle giving us $\lceil \tfrac{n-1}{2} \rceil$ total moves. So our minimum value which is attainable is indeed $m=n-1 + \lceil \tfrac{n-1}{2} \rceil$. $\square$

We claim the answer is $\frac{3n-3}{2}$ for odd $n$ and $\frac{3n-2}{2}$ for even $n$, which is equivalent to $\lfloor \frac{3n-2}{2} \rfloor$ as many above me have pointed out. We will prove using induction. The bases cases are trivial: $n=3$ and $n=4.$ For $n=3$ we have a triangle. For $n=4$ we have $K_4$ but we remove any edge. It is clear that these are minimal values. Now for the inductive hypothesis assume the values provided above are minimal for $2k$ and $2k+1$ vertices. When there are $3k+2$ vertices we can draw any triangle between any 3 points, as it is isomorphic/automorphic to the minimal graph. Now contract the triangle into a single point. This is our inductive hypothesis for $2k.$ We can do a similar thing on $3k+3$ vertices, and then our induction would be complete. Q.E.D.