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

-
Thank you. I just started a graph theory course last week so I don't have a global view of what questions may be like, but have seen a few times this idea of starting with something small and letting it grow (as you did it) inside a graph. Is this idea consistently powerful and frequent throughout the subject or is just so at the entry level? – Chuwei Zhang Oct 10 '12 at 18:59

This is a classic problem where the Probabilistic Method gives a very nice solution.

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
Hi, can you please elaborate why expected m/2 implies positive probability? (Is this related to Markov's inequality?) – user1685224 Nov 28 '14 at 15:29
@user1685224 Suppose $X$ is a discrete random variable on a discrete probability space $(\Omega, \mathcal{P}(\Omega), \mathbb{P})$, where the probability measure $\mathbb{P}$ is given by a probability mass function $p$, where$\sum_{\omega \in \Omega} p(w) = 1$. Then $\mathbb{E}(X) \geq r$, where $r \in \mathbb{R}$ implies that there exists $\omega \in \Omega$ such that $X(w) \geq r$. This is because if $X < r$ everywhere on $\Omega$, then $\mathbb{E}(X) = \sum_{\omega \in \Omega} X(w) p(w) < \sum_{\omega \in \Omega} r p(w) =r \sum_{\omega \in \Omega} p(w) = r$. – Ilham May 23 '15 at 21:48
@user1685224 The existence of such a $\omega$ does not always imply that $\mathbb{P}(X \geq r) >0$ since the set of such $\omega$ may be null, but it doesn't matter here, since all we need is the existence. – Ilham May 23 '15 at 21:59