A cut with an odd number Let $G = (V,E)$ be an undirected connected graph. Let $F$ be a subset of $E$ such that $F$ does not induce a cut in $G$ (i.e. it is impossible to partition $V$ into two disjoint sets $A$ and $B$ such that the set of edges that cross $A$ and $B$ is $F$). Show that there is a set of edges $S \subseteq E$ such that the degree of every vertex in the graph $(V,S)$ is even and $|F \cap S|$ is odd.
First, I tried to see if it is possible to get a cut that contains $F$, e.g., by considering the graph $(V,F)$. If it is not bipartite than it has an odd cycle, and so the set of its edges $C$ shows that $|F \cap C|$ is odd, but how do we prove the general case?
 A: My comment wasn't very good, but your answer made it possible to understand the problem. I found it very interesting. I've got quite a long reasoning. This is in spite of the fact that I did not write down some of the details.
The proof is by induction on $|F|$.
1) Let $|F|=1$ and $F=\{e\}$, $e=uv$, $u,v\in V(G)$.
If the graph $G-e$ is connected, then
there exists a path $P$ in $G-e$ connecting $u$ and $v$.
So $C=P+e$ is a cycle and $|C\cap F|=1$.
If $G-e$ is not connected, then $F$ induces a cut in $G$.
2) Let $|F|\geq2$ and $e=uv\in F$.
2A) If $G-e$ is not connected, then $G-e$ has two components, say $A$ and $B$.
We have $F-e=(A\cap F)\cup (B\cap F)$.
For example, let $A\cap F$ not induce a cut in $A$.
By induction, there is a set of edges $S\subset E(A)$ such that the degree of every vertex in the graph $(V(A),S)$ is even and $S\cap(A\cap F)$ is odd.
It is clear that $S$ is the set we are looking for.
If $A\cap F$ induces a cut in $A$ and $B\cap F$ induces a cut in $B$, then
it is easy to see that $F$ induces a cut in $G$.
2B) Let $G-e$ is connected.
If $F-e$ does not induce a cut in $G-e$, then the proof ends by induction.
Let $F-e$ induce a cut in $G-e$.
Let $V=A\cup B$, $A\cap B=\varnothing$ and
let the set of edges that cross $A$ and $B$ be $F$.
If $u\in A$ and $v\in B$ or $u\in B$ and $v\in A$, then $F$ is a cut of $G$.
Now let $u,v\in A$.
Denote by $X$ and $Y$ the induced subgraphs of $G-e$ by the sets $A$ and $B$, respectively.
Let $X_1,\ldots,X_s$ be the components of $X$ and $Y_1,\ldots,Y_t$ be the components of $Y$.
Let moreover $u\in X_i$, $v\in X_j$.
We can assume that $i\neq j$ otherwise we can construct a cycle containing a single edge from $F$ and this edge is $e$.
Since the graph $G-e$ is connected, there exists an alternating sequence of components:
$$
X_i,Y_{r_1},X_{t_1},\ldots,X_{t_p},Y_{r_q},X_j
$$
such that any two neighboring components are connected by an edge, and this edge can only be an edge of $F$.
If necessary, add edges from components to obtain a path $P$ connecting vertices $u$ and $v$ in the graph $G-e$. The path $P$ contains an even number of edges of $F$.
So  $C=P+e$ is a cycle and $|C\cap F|$ is odd.
