Intuition: Odd-cycle transversal in triangle-free graphs I conjecture that if $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle.

For more information, see the 1988 paper by Erdös et al., How to Make a Graph Bipartite.

Question 1: Is this conjecture true by your intuition?

Question 2: What is the complexity of counting the number of odd cycles in a graph? Is there any efficient algorithm to do that?
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)})$.