Prove that there exists a bipartite subgraph containing at least half of the edges in the original graph.

Question

Prove that there exists a bipartite subgraph containing at least half of the edges in the original graph.

Answer 1

This can be proved by induction on the number of nodes $n$ in the graph. Clearly the base case of $n = 0$ (or $n = 1$) is true, as there are no edges. Now, imagine adding a node to a graph $G$ to create a new graph $G'$. By induction, we know that $G$ has a bipartite subgraph containing at least half of its edges. Let $U$ and $V$ be the partitions of nodes of this bipartite subgraph. Now, consider the new node added to $G$ to form $G'$. Every one of its edges is connected to a node in either $U$ or $V$, so by the appropriate use of the pigeonhole principle, at least half of it's edges are connected into $U$ or into $V$. WLOG, let's say at least half the edges are connected into $U$. Then we can easily form a bipartite subgraph on $G'$ by adding the new node to $V$, and ignoring all its other edges.