-2

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

anasanzari
  • 33
  • What if my original graph is complete? ... – user2097 Aug 29 '15 at 19:38
  • 1
    @user2097 Well $K_{2n}$ has $\binom{2n}{2} = 2n^2-n$ edges, while the largest bipartite subgraph $K_{n,n}$ has $n^2$ edges. Clearly $n^2 > \frac{2n^2-n}{2}$, so it works in that case. For $K_{2n+1}$ we have $\binom{2n+1}{2} = 2n^2+n$ edges, and $K_{n+1,n}$ has $n^2+n > \frac{2n^2+n}{2}$ edges, so we're good there too. I think you missed the "at least half" part. – 727 Aug 29 '15 at 19:57
  • 4
    Your question has been asked (and answered) already: http://math.stackexchange.com/questions/289537/show-that-every-graph-g-has-a-bipartite-subgraph-with-at-least-half-of-the-edg – 727 Aug 29 '15 at 20:05

1 Answers1

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.

Colm Bhandal
  • 4,649