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

(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.

• Part (i) is well-known in the form "any set of $n$ politicians can be split into two parties such that each politician has at least as many enemies in the opposite party as in their own". Apr 2 '19 at 17:16

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.