Bipartite subgraph
Task number: 3604
Show that every graph with \(m\) edges has a bipartite subgraph with at least \(\frac{m}2\) edges.
Hint
Imagine that you are building the graph by adding one vertex at a time.
Solution
We proceed by induction on the number of vertices (the assertion holds for a one-vertex graph).
Choose an arbitrary vertex \(u\). Consider \(G'=G\setminus u\); by the inductive hypothesis \(G'\) has a bipartite subgraph with at least \(\frac{|E_{G'}|}2\) edges. Let \(A\) and \(B\) be the parts (partitions) of this bipartite graph.
We will expand one of these parts by adding \(u\) in such a way that we may add at least \(\frac{\deg_G(u)}2\) edges to the bipartite graph – which is certainly possible if we add \(u\) to the part in which it has fewer neighbors.
The resulting bipartite subgraph has at least \(\frac{|E_{G'}|}2+\frac{\deg_G(u)}2=\frac{|E_{G}|}2\) edges.
