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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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|$.
Answer that question and fill in the details of the argument, and you’ll have your induction step.