Question

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!

Answer 1

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.