2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – PhiB
    Sep 8, 2013 at 14:49
  • $\begingroup$ @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. $\endgroup$ Sep 8, 2013 at 18:05
  • $\begingroup$ Oh, OK! I totally see that now. Thank you. $\endgroup$
    – PhiB
    Sep 8, 2013 at 22:47
  • $\begingroup$ @PhiB: You’re welcome. $\endgroup$ Sep 9, 2013 at 3:07
  • $\begingroup$ 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. $\endgroup$
    – PhiB
    Sep 9, 2013 at 15:28

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.