How do I show that a loopless graph contains a spanning graph with certain properties? [closed]

Solution 1:

Color the vertices of your graph $\color{red}{red}$ or $\color{blue}{blue}$ in such a way that maximizes the number of edges with extremes $\color{red}{red}$ and $\color{blue}{blue}$.

Consider now the spanning subgraph with every edge with extremes $\color{red}{red}$ and $\color{blue}{blue}$. Of course it's bipartite, because it connects only vertices of different colors. Also, if the degree of a vertex $x$ in this new graph was less than $\deg(x)/2$, switching the color of $x$ would increase the number of edges with extremes $\color{red}{red}$ and $\color{blue}{blue}$ in the original graph, contradicting it's maximality. Therefore, this spanning subgraph has the desired proprieties.