0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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". $\endgroup$ Apr 2 '19 at 17:16
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.