Graph Theory: Graph with bipartite subgraph has MORE than e(G)/2 edges.

Show that every loopless graph G has a bipartite subgraph with more than e(G)/2 edges. Use induction on the number of vertices.

Clearly if n(G) = 2, the hypothesis holds. But I am not sure how to formulate the induction step.

HINT: The strict inequality is actually false for the graph with two vertices and no edges; in all other cases, however, it holds.

Suppose that every graph with $n$ vertices has the desired property, and let $G$ be a graph with $n+1$ vertices. Let $v$ be any vertex of $G$, and let $G'$ be the subgraph of $G$ that remains after you remove $v$ and the edges incident at $v$. $G'$ has $n$ vertices, so either it has a bipartite subgraph $H$ with more than $\frac12e(G')$ edges, or $n=2$ and $G'=H$ has no edges.

Let $A$ and $B$ be the parts of $H$, and let $W$ be the set of vertices in $G'$ that are joined to $v$ by an edge of $G$. Without loss of generality $|W\cap A|\ge|W\cap B|$.

• To which of $A$ and $B$ should you add $v$, and which edges at $v$ should you keep, in order to expand $H$ to a bipartite subgraph of $G$ with more than $\frac12e(G)$ edges?

Answer that question and fill in the details of the argument, and you’ll have your induction step.

• I am not sure about that... If you add v to B and keep the edges which already had one endpoint in B, would that give you over half the edges of G in B?
– PhiB
Sep 8, 2013 at 14:49
• @PhiB: If you add $V$ to $B$ and keep the edges in $H$ and the edges from $v$ to $A$, you’ll have a bipartite graph with more than $\frac12e(G)$ edges. Sep 8, 2013 at 18:05
• Oh, OK! I totally see that now. Thank you.
– PhiB
Sep 8, 2013 at 22:47
• @PhiB: You’re welcome. Sep 9, 2013 at 3:07
• I need one bit of clarification: when we say "...either it has a bipartite subgraph H with more than 1/2 e(H) edges, ...", don't we really mean 1/2 e(G') edges? H has all of H's edges.
– PhiB
Sep 9, 2013 at 15:28