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

  • 1
    $\begingroup$ I could not understand your question until I read the original at M.SE, maybe you should reword the beginning in a similar fashion. $\endgroup$
    – domotorp
    Sep 8 '14 at 20:56
  • $\begingroup$ I added a sentence to the first paragraph to get the phrasing from the M.SE question as well. $\endgroup$
    – CoffeeCat
    Sep 8 '14 at 22:17
  • $\begingroup$ 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). $\endgroup$
    – 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:

a sequence of edge removals

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: a sequence of edge removals

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$.

  • $\begingroup$ Or 8 edges also. (Start by removing the red square.) $\endgroup$ Sep 9 '14 at 8:26
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 9 '14 at 8:34
  • $\begingroup$ +1 for pretty graphs $\endgroup$
    – bbejot
    Sep 9 '14 at 16:33
  • $\begingroup$ I don't understand your second edit: what about the complete bipartite graph with $n/2+n/2$ vertices? $\endgroup$ Sep 9 '14 at 16:52
  • $\begingroup$ 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. $\endgroup$ Sep 9 '14 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.