TITLE: Find an edge subset such that the graph is bipartite.
QUESTION [0 upvotes]: Let $G$ be a undirected Graph. Find the minimal subset of edges $F$ such that $G$ without $F$ is bipartit.
Prove that this is possible in linear time, meaning Number of Nodes + Number of Edges.
I already know that a graph is bipartit if they do not contain a cycle with an odd number of nodes.
I am also aware that it is possible to decide whether a graph contains a circle and whether it has odd number of nodes in linear time using Depth-First Search.
The problem is that this only findes a cycle and not all. 
Is this approach even right and if yes how do I need to adapt it and if not what would be a better approach?

REPLY [1 votes]: Finding a minimal set $F$ [see my comments above] is more straightforward--and I suspect what you were asking for: Let us assume WLOG that $G$ is connected, and let $T$ be a BFS spanning tree, starting from an arbitrary vertex $v$. Let $L_i$ be the set of vertices of distance precisely $i$ from $v$ in $T$ for each integer $i=0,1,2,\ldots$ (then $L_i$ is also the set of vertices of distance precisely $i$ from $v$ in $G$ for each such $i$). Then every edge $e$ in $G \setminus E(T)$ satisfies either one or the other of the following:
(a) there is an $i$ such that one endpoint of $e$ is in $L_i$ and the other in $L_{i+1}$, OR
(b) there is an $i$ such that both endpoints of $e$ are in $L_i$.
Let $F$ be the set of edges that satisfy (b). Then $F$ is a minimal set of edges such that $G \setminus F$ is bipartite. 
See if you can see why. HINT: Iff $e$ has both endpoints in $L_i$ for some $i$ then $e$ induces an odd cycle with $T$. However, if every edge in $G \setminus T$ satisfies (a), then every path alternates from a vertex in $L_i$; $i$ odd, to a vertex in $L_{i'}$, $i'$ even. This implies only even-length cycles.

[If you were asking for a minimum such set $F$ then the above doesn't answer the question. I am not positive either way but finding a minimum such $F$ does seem to be hard to me.]
{"set_name": "stack_exchange", "score": 0, "question_id": 3043032}