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.
Asked
Active
Viewed 601 times
0
-
greedy (2-coloring of vertices) algo will split vertices into two sets with at least half the edges in cut. – dEmigOd Jul 14 '19 at 19:02
-
your solution seems also viable – dEmigOd Jul 15 '19 at 08:47
1 Answers
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.
dEmigOd
- 3,308
-
Thank you, how about my solution to disconnect odd cycles, do you think it is legit? – user2743516 Jul 15 '19 at 08:19