Given any graph $G$, can we find a bipartite subgraph of $G$ with at least $e(G)/2$ edges ($e(G)$ is the number of edges in $G$) by sequentially deleting the edge belonging to the most number of odd cycles? That is, if we take a graph and sequentially delete the edge which belongs to the most odd cycles until we have a bipartite graph, will at least half the edges remain when the graph is bipartite?
The motivation is to find a a simple method for making a graph bipartite making use of the odd cycle-free interpretation of bipartiteness rather than the $2$ color class viewpoint.
Note: I asked this question on M.SE. I expected I was missing some simple argument or counterexample, but no one has given an answer so perhaps it is more tricky: https://math.stackexchange.com/questions/913366/a-method-of-making-a-graph-bipartite Edit: clarity