# In a graph, the vertices can be partitioned $V=V_1\cup V_2$ so that at most half of all edges run within each part?

I am thinking of destroying all cycles of odd length by removing edges, so that I get a bipartite graph, with a partition $V_1$ and $V_2$ so that no edge in the new graph run within the two parts. Then the worst case in adding back the edges I removed, is that these edges all run within each part. So I would like to show that I can destroy all odd cycles by removing at most half of all the edges. Anyone can tell me if I am thinking in the right direction?

-
this looks to be a duplicate of this question. One should be closed. –  robjohn Jan 29 '13 at 17:02

Consider starting with a graph $G$ and partitioning its vertices into $V_1$ and $V_2$ by looking at each vertex one by one and assigning it to $V_1$ or $V_2$ (starting with $V_1$ and $V_2$ both empty): if the vertex $v$ has more edges going to $V_1$ than $V_2$, assign it to $V_2$, otherwise assign it to $V_1$. If you assign $v$ to $V_i$, colour each edge from $v$ to $V_i$ red and every edge from $v$ to $V_{3-i}$ blue. Then there will always be at least as many blue edges as red edges. When the process is finished, all edges will be coloured, those within $V_1$ or $V_2$ will be red and those between $V_1$ and $V_2$ will be blue.
Consider the effect of randomly assigned each vertex, independently and identically, to $V_1$ or $V_2$ with probability $1/2$. In this case, the expected number of edges that cross the two halves is $m/2$. This implies that there is a positive probability of partitioning the vertices so that the actual (as opposed to expected) number of edges crossing the two halves is at least $m/2$. In particular, such a partition exists.
Thank you. I am surprised (positively) because probability builds on combinatorics but can be used to give intuitions back to combinatorics. Can you maybe use the same argument to show that we can in addition require each $V_i$ to span fewer than a third of all the edges? This is the second subquestion of the problem I am trying to solve. –  Chuwei Zhang Oct 10 '12 at 21:56