Prove that every simple graph $G$ contains a spanning subgraph, which is bipartite and $\deg(v') \geq \frac{1}{2}\deg(v)$.

Question

(i) Prove that every finite simple graph $G$ contains a spanning subgraph $H$ (i.e., $V (G) = V (H)$) such that $H$ is a bipartite graph, and for every vertex $x \in V(G)$, the degree of $x$ in $H$ is at least half of the degree of $x$ in $G$, i.e.,$$\deg_{H}(x)\geq\frac{1}{2}\deg_{G}(x).$$

(ii) Conclude from part (i) that every finite simple graph contains a bipartite subgraph with at least half of the edges.

Answer 1

Start with any partition $V_1, V_2$ of the vertices of $G$.

Move every vertex $v$ of $V_1$ that has more neighbours in $V_1$ than in $V_2$ to $V_2$ and do the same the vertices of $V_2$. The resulting bipartite graph with parts $V_1,V_2$ has the desired property.