Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
this looks to be a duplicate of this question. One should be closed. –  robjohn Jan 29 '13 at 17:02

2 Answers 2

up vote 4 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|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|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

Your Answer

 
discard

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.