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?
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.]