show that a loopless graph $G$ contains a bipartite spanning subgraph $H$ such that $d_H(v) \ge \frac{1}{2} d_G(v)$ for all v $\in$ V.

Question

The hint in the appendix of book says that bipartite subgraph with with largest possible number of edges has such a property, but I don't know how to use this hint!

any help would be appreciated.

Answer 1

I'm not sure what "maximal bipartite graph" means. If it means "bipartite spanning subgraph with the maximum possible number of edges" then the hint is correct. Hint. Let $H$ be such a graph, with bipartition $(V_1,V_2)$. Assume for a contradiction that there is a vertex $v\in V$ -- without loss of generality, $v\in V_1$ -- such that $d_H(v)\lt \frac12d_G(v)$. In other words, $v$ has more neighbors in $V_1$ than in $V_2$. [*] Show that, by moving $v$ from $V_1$ to $V_2$, we get a bipartite spanning subgraph with more edges than $H$, contradicting the assumed maximality.

[*] Let $N_G(v)$ be the set of all vertices adjacent to $v$ in the graph $G$. Since $v\in V_1$, we have $$d_H(v)=|N_G(v)\cap V_2|$$ and $$d_G(v)=|N_G(v)|=|N_G(v)\cap V_1|+|N_G(v)\cap V_2|.$$ Thus the assumption $$d_H(v)\lt \frac12d_G(v)$$ is equivalent to $$|N_G(v)\cap V_1|\gt|N_G(v)\cap V_2|$$ which is what I meant by "$v$ has more neighbors in $V_1$ than in $V_2$".