Intuition: Odd-cycle transversal in triangle-free graphs
My intuition says it's probably true, and here's a matching lower bound (i.e. a graph of which you have to delete at least $\frac{n^2}{25}$ edges for it to become bipertite:

$G=(V_1\cup V_2\cup V_3\cup V_4\cup V_5, (V_1\times V_2) \cup (V_2\times V_3) \cup (V_3\times V_4) \cup (V_4\times V_5) \cup (V_5\times V_1))$
, $|V_1| = |V_2| = |V_3| = |V_4| = |V_5|$.

This graph is certainly triangle free, but if $x&lt;\frac{n^2}{25}$ edges are to be deleted there will still exist a $C_5=v_1\to v_2\to v_3\to v_4\to v_5 \to v_1$  for some vertices $v_1\in V_1, v_2\in V_2, v_3\in V_3, v_4\in V_4, v_5\in V_5$.

As for the second question, it is well known that counting simple cycles of length $2k+1$ are $\#W[1]-hard$, with respect to $k$, and can't be computed in time $n^{o(k)}$ unless ETH fails.

There is, however, a possibility to approximate the number of such cycles in $O^*(2^{O(k)})$.