Prove there always exists a partition such that vertices in each part have even degree

We approach this problem via induction on the number of vertices, $|V|$. Trivially, the claim is true when $|V|\leq 3$.

Assume for our induction hypothesis that all graphs on strictly fewer than $n$ vertices satisfies the claim that there exists some partition into two sets of vertices where the induced subgraph on each is such that every vertex is of even degree. Consider then what happens for arbitrary $G$ when $|V(G)|=n$.

We may assume that $G$ contains at least one vertex of odd degree (if not, then take $V_1 = V$ and $V_2 = \emptyset$, trivially satisfying the claim). Pick one such vertex of odd degree and label it $v$. Take note of the neighborhood of $v$ and label it $\mathscr{N}(v)$.

Construct a new graph from the original defined as: $G' = (V(G)\backslash\{v\}, \{(x,y):~x\neq y, (x,y)\in E(G\backslash \mathscr{N}(v))\cup (E(\mathscr{N}(v)))^c\})$

That is to say, to form $G'$, invert the adjacency relationships between members of $\mathscr{N}(v)$, delete $v$, and retain the rest of the graph the way it was in $G$.

Now, $G'$ has fewer vertices than $G$ and by our induction hypothesis has some partition $V_1', V_2'$ such that all vertices in the induced subgraphs from $G'$ are of even degree.

Define $A = V_1'\cap \mathscr{N}(v)$ and define $B = V_2'\cap \mathscr{N}(v)$

As $v$ was selected to be of odd degree, precisely one of $|A|$ or $|B|$ will be of even size. Without loss of generality, assume it was $A$.

Returning now to the original graph, consider the partition $V_1 = V_1'\cup\{v\}$ and $V_2 = V_2'~~~~~$ (note, if it had been $B$ which was of even size, attach $\{v\}$ to $V_2$ instead)

Note that for any vertex $x\in V_i\backslash\mathscr{N}(v)$, the adjacencies are the same as in the induced subgraph from $G'$ of $V_i'$, and is therefore of even degree.

For any vertex in $A$, It will have the same number of adjacencies to elements outside of $A$ as in the induced subgraph from $G'$ of $V_1'$ (either odd or even$\star$), and will have $|A\backslash\{x\}|$ minus the number of adjacencies to other elements of $A$ while in $G'$ (odd if $\star$ was odd, even otherwise), plus 1 for the adjacency to $v$. I.e., $d_{G(V_1)}(x) = d_{G'(V_1')}(x) + |A|-1-d_{G'(A')}(x)+1$ (which is even + even - 1 - even + 1 or it is odd + even - 1 - odd + 1) and is therefore of even degree.

For any vertex $x\in B$, as $|B|$ was assumed to be odd, it will similarly be $d_{G(V_2)}(x) = d_{G'(V_2')}(x) + |B|-1 -d_{G'(B')}(x)$ (which is even + odd - 1 - even or it is odd + odd - 1 - odd) and is also of even degree.

For $v$ itself, its only adjacencies are to $A$, which was assumed to be of even size, and so $d(v)=|A|$ is even.

Therefore, all vertices are of even degree in their respective induced subgraphs and the claim is proven.