The only remaining case is when all the degrees are even. For graphs on 2 vertices, this is easy to verify to be true.

Now let's solve the problem for the case when there are $$$2n \ge 4$$$ vertices. If all vertices are isolated, we are done. Else, consider any edge $$$(u, v)$$$. Loop over the neighbours $$$x$$$ of $$$u$$$ and the neighbours $$$y$$$ of $$$v$$$, and toggle the existence of the edge $$$(x, y)$$$ each time. Now remove $$$(u, v)$$$ from the graph. The resulting graph $$$G'$$$ is also a graph with all even degrees, and is on $$$2(n-1)$$$ vertices, so it satisfies the inductive hypothesis.

So there is a partition of the vertices of $$$G'$$$ into two non-empty sets such that the degrees of the vertices in the subgraphs of $$$G'$$$ induced by the partition are all even. Now we only need to add back $$$u$$$ and $$$v$$$ into these subgraphs and preserve the condition. Note that $$$(u, v)$$$ was an edge, so the remaining number of neighbours of $$$u$$$ in the original graph is odd. So exactly one partition has an odd number of neighbours of $$$u$$$, and the same goes for $$$v$$$. We will add $$$u$$$ to the partition with an odd number of neighbours of $$$v$$$ and vice versa — it is easy to verify that this works (in fact, we have a bijection, so there is exactly one way, modulo swapping, to partition the vertices suitably).