5
$\begingroup$

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?

  • 0
    this looks to be a duplicate of [this question](http://math.stackexchange.com/q/289537). One should be closed.2013-01-29

2 Answers 2

7

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.

  • 0
    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?2012-10-10
4

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.

  • 0
    @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.2015-05-23