Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am reading "introduction to graph theory" written by Douglas. I try to understand the proof of 1.3.19 theorem from this book but I failed... Here is the statement.

$\text{Every loopless graph G has a bipartite subgraph with at least e(G)/2 edges.}$

Author starts with any partition $V(G)$ into two sets $X,Y$. Using the edges having one endpoint in each set yields a bipartite subgraph $H$ with bipartition $X,Y$. He said that if $H$ contains fewer than half the edges of $G$ incident to a vertex $v$, then $v$ has more edges to vertices in its own class than in the other class. Moving $v$ to the other class gains more edges of $G$ than it loses.

I do not understand why the last two sentences are true. Could anyone give some example or detailed description about this theorem? Thanks!

share|improve this question
add comment

closed as off topic by Brendan McKay, Chris Godsil, Igor Rivin, Benjamin Steinberg, Andreas Blass Mar 6 '12 at 16:13

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 3 down vote accepted

We start with any partition of $V(G)$ into two sets $X$ and $Y$. Using the edges having one endpoint in each set yields a bipartite subgraph $H$ with partitions $X$ and $Y$.

If $H$ has at least $\frac{e(G)}{2}$ edges, the proof is complete.

If for each vertex $x$ of $H$, $d_H(x) \geq \frac{d_G(x)}{2}$, then by applying degree-sum formula we have $e(H) \geq \frac{e(G)}{2}$ and the proof is complete.

Suppose that there is a vertex in one partition of $H$, say $\nu \in X$, that $d_H(\nu)< \frac{d_G(\nu)}{2}$. We move $\nu$ from $X$ to $Y$. So, now $d_H(\nu) \geq \frac{d_G(\nu)}{2}$.

We repeat this algorithm until for each vertex $x$ of $H$, $d_H(x) \geq \frac{d_G(x)}{2}$. It is clear that this algorithm must terminate. Now by by applying degree-sum formula we have $e(H) \geq \frac{e(G)}{2}$ and the proof is complete.

This Idea of proof is well-known and its name is switching method.

share|improve this answer
add comment

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