Show that every graph has a bipartite subgraph with at least half of its edges

Question

I know that there are solutions where we use induction. but i have a solution, and i think it is legit. let $c_1, c_2 ... , c_k$ be all the odd circles in graph $G$, the smallest circle would be a triangle , so we can remove from every one of them an edge, so it breaks the circle, like that, we end up removing at most $e(G)/3$ of the edges, the subgraph we got has no odd circles, so it is a bipartite. i may miss something, wish for your opinions. Thanks.

Answer 1

I'll shortly describe how to color a connected graph in two colors ($1$ and $2$), then just apply to any connected component.

• Order all vertices [in arbitrary order]
• While there are un-colored vertices
  • pick the first vertex in the list and color it in a way that maximize the number of edges going through the cut (between color $1$ and color $2$). E.g. if picked vertex have $x$ color-$1$ neighbors and $x+y$ color-$2$ neighbors, then color in color $1$.

It is easy to see, that at least half of the edges connect vertices of one color to vertices of the other. Drop edges between same-colored vertices and you are done.