# A method for making a graph bipartite

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

• I could not understand your question until I read the original at M.SE, maybe you should reword the beginning in a similar fashion. Sep 8 '14 at 20:56
• I added a sentence to the first paragraph to get the phrasing from the M.SE question as well. Sep 8 '14 at 22:17
• You might also mention more explicitly the other part of your math.se question, that you are not interested in the greedy max-cut approach (or I guess that's what your second paragrap means).
– usul
Sep 9 '14 at 7:22

A quick check with Mathematica seems to suggest that a (smallest) counterexample is given by a graph with 6 vertices and 13 edges:

Here the red edges are contained in the most odd cycles (16, 12, 6, 5, 2, 2, 1, 0 respectively) and one possible sequence of edge removals is shown. However, choosing different edges one can end up with a bipartite graph with 7 edges.

Edit: Any sequence of edge removals of the following graph with 8 vertices and 18 edges seems to result in a bipartite graph with at most 8 edges:

Edit: For those interested: here's the Mathematica code to check that the last graph is really a counterexample.

Edit: The first complete graph for which the algorithm fails is the complete graph on 10 vertices. Indeed, it seems that the largest bipartite graph one can obtain from an $$n$$-vertex ($$n>4$$) complete graph is the complete bipartite graph on $$(n-3)+3$$ vertices, which has $$3(n-3)$$ edges, i.e. smaller than $$n(n-1)/4$$ for $$n\geq 10$$.

• Or 8 edges also. (Start by removing the red square.) Sep 9 '14 at 8:26
• Yes, you are right. I guess the real question is: do graphs exist for which any sequence of edge removals (belonging to most odd cycles) leads to a bipartite graph with less than $e(G)/2$ edges. Sep 9 '14 at 8:34
• +1 for pretty graphs Sep 9 '14 at 16:33
• I don't understand your second edit: what about the complete bipartite graph with $n/2+n/2$ vertices? Sep 9 '14 at 16:52
• Not all bipartite subgraphs can occur as result of the algorithm. It turns out that (at least I checked for $5\leq n\leq 11$) that the largest such subgraph that can occur is the $(n-3)+3$ one. One should probably carefully consider the possibilities at each step to understand why, or perhaps there is a simple argument that I don't know. Sep 9 '14 at 17:08