Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
this looks to be a duplicate of this question. One should be closed. – robjohn Jan 29 '13 at 17:02
up vote 6 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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