how to proof "every loopless graph G has a bipartite subgraph with at least e(G)/2 edges"? [closed]

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 have a graph where I can't manage to create a subgraph meeting the condition where each vertex has at least half as many adjacent edges as in the full graph. Can anyone show me the bipartite subgraph that meets the condition?

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.