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 graph with no odd cycles is called a bipartite graph because the vertex set of such a graph can be partitioned into two sets $V_1$ and $V_2$ so that every edge has one endpoint in $V_1$ and the other in $V_2$.
Proposition. Any graph $G=(V,E)$ has a bipartite subgraph which contains at least half the edges of $G$. (In other words, if $G$ has $n$ edges, then $G$ can be made bipartite by removing at most $n/2$ edges.)
[P.S. A comment by user Paralyzed_by_Time provided references for this observation: Paul Erdős, Ralph Faudree, János Pach, and Joel Spencer, How to make a graph bipartite, J. Combin. Theory Ser. B 45 (1988), 86–98 and (apparently the original reference) P. Erdős, On some extremal problems in graph theory, Israel J. Math. 3 (1965), 113–116.]
Proof. Partition $V$ into two sets $V_1,V_2$ in a way that maximizes the number of edges that cross between $V_1$ and $V_2$. Note that each vertex has at least as many neighbors on the other side of the partition as on its own side; otherwise moving $v$ to the other side would increase the number of cross-edges, contradicting the assumed maximality of the partition. From this it easily follows that at least half the edges of $G$ cross between $V_1$ and $V_2$, i.e., the bipartite graph with those edges contains at least half the edges of $G$.
In general we can't do too much better than delete half the edges, because of the following example. The complete graph $K_t$ has $n=\binom t2=\frac{t^2-t}2$ edges, and its largest bipartite subgraph has $\lceil\frac t2\rceil\cdot\lfloor\frac t2\rfloor=\lfloor\frac{t^2}4\rfloor$ edges, so we have to delete almost half the edges of $K_t$ to get a bipartite graph.
Best Answer
I think this is a hard exercise if you don't know the trick. I'll show a proof of Mantel's Theorem which uses the same idea, as a hint.
Proof of the exercise: Let $G$ be a graph on $n$ vertices. For every edge $xy\in E$ denote the number of triangles which contain $x$ and $y$ as $t_{xy}$; in particular, $t_{xy}$ is the number of common neighbours of $x$ and $y$. Thus $d(x)+d(y)\leq n+t_{xy}$; by summing this inequality over the edges: $$\sum_{xy\in E}(d(x)+d(y))\leq n\cdot|E|+\sum_{xy\in E}t_{xy}$$ Note that each triangle in $G$ is counted exactly three times in the second terms of RHS; for example, if $xyz$ is a triangle then it is counted in $t_{xy},t_{yz},t_{zx}$. Thus $$\sum_{xy\in E(G)}(d(x)+d(y))\leq n\cdot|E|+3\cdot t(G)$$ By proceeding exaclty as before, we get that $$\frac{4\cdot|E|^2}{n}\leq n\cdot|E|+3\cdot t(G)$$ $$\implies t(G)\geq \frac{1}{3}\left(\frac{4\cdot|E|^2}{n}-n\cdot|E|\right)$$ $$\implies t(G)=|E|\cdot\frac{4|E|-n^2}{3n}$$