most recent 30 from http://mathoverflow.net 2013-05-19T20:30:29Z http://mathoverflow.net/feeds/question/90343 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90343/how-to-proof-every-loopless-graph-g-has-a-bipartite-subgraph-with-at-least-eg Mathsniper 2012-03-06T10:33:12Z 2012-03-06T11:41:13Z

<p>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.</p> <p>$\text{Every loopless graph G has a bipartite subgraph with at least e(G)/2 edges.}$</p> <p>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.</p> <p>I do not understand why the last two sentences are true. Could anyone give some example or detailed description about this theorem? Thanks!</p>

http://mathoverflow.net/questions/90343/how-to-proof-every-loopless-graph-g-has-a-bipartite-subgraph-with-at-least-eg/90355#90355 Zahra 2012-03-06T11:41:13Z 2012-03-06T11:41:13Z

<p>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$.</p> <p>If $H$ has at least $\frac{e(G)}{2}$ edges, the proof is complete.</p> <p>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.</p> <p>Suppose that there is a vertex in one partition of $H$, say $\nu \in X$, that $d_H(\nu)&lt; \frac{d_G(\nu)}{2}$. We move $\nu$ from $X$ to $Y$. So, now $d_H(\nu) \geq \frac{d_G(\nu)}{2}$.</p> <p>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.</p> <p>This Idea of proof is well-known and its name is switching method.</p>