Problem: Given a graph G and a positive integer $k$, does there exist a $G' \subseteq G$ containing exactly $k$ edges, such that all vertices of $G'$ are of odd degree.
Is this problem NP-Hard or is it in P?
I tried finding a reduction from 3SAT and Clique.
Reduction from SAT seems to be impossible because we are allowed to delete arbitrary edges and not have an induced subgraph. So any widget we construct can be broken by the solver of ODD-SUBGRAPH.
Reduction from Clique seems promising.
W.l.o.g we can assume $k$ is even, then there exists a $k$-Clique $\implies$ there exists an odd degree subgraph of $k(k-1)/2$ edges.
(If $k$ is odd, we can add a vertex $v$ and connect it to all existing vertices in the input graph and solve for $k' = k+1$, because existence of $k$-clique in input graph $\iff$ existence of $k+1$ clique in the new graph)
But the converse doesn't hold.
I also tried preprocessing the input graph to remove all vertices of degree less than $k-1$ because they are not part of a $k-$Clique. But I'm not able to use it to say that if there exists an odd degree subgraph with exactly $k(k-1)/2$ edges, a $k-$clique must also exist.
Actually I think this is in P because you can reduce most of it to a system of equations mod 2
For each edge (u,v) in G construct a variable $x_{\{u,v\}}$ with $x_{\{u,v\}} \equiv_2 1 \leftrightarrow \{u,v\} \in G'$ and $x_{\{u,v\}} \equiv_2 0 \leftrightarrow \{u,v\} \notin G'$
Then you have, for each $u$, an equation $\sum\limits_{v \in n(u)} x_{\{u,v\}} \equiv_2 1$ where $n(u)$ is the set of neighbors of $u$
You can solve the system using Gaussian elimination.
The problem that remains (and I can't quite figure out) is ensuring the number of positive variable assignments is equal to $k$.