16
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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
    Commented Sep 8, 2014 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
    Commented Sep 8, 2014 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
    Commented Sep 9, 2014 at 7:22

1 Answer 1

Reset to default
21
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Or 8 edges also. (Start by removing the red square.) $\endgroup$
    – The Masked Avenger
    Commented Sep 9, 2014 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$
    – Timothy Budd
    Commented Sep 9, 2014 at 8:34
  • $\begingroup$ +1 for pretty graphs $\endgroup$
    – bbejot
    Commented Sep 9, 2014 at 16:33
  • $\begingroup$ I don't understand your second edit: what about the complete bipartite graph with $n/2+n/2$ vertices? $\endgroup$
    – Benoît Kloeckner
    Commented Sep 9, 2014 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$
    – Timothy Budd
    Commented Sep 9, 2014 at 17:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .