Split graph in two parts, such that most nodes have even number of edges

Question

We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between nodes of different parts are destroyed and not counted.

All possible splittings are allowed, even the one where all nodes are in one part. Each node should be in one part, we are required to print the nodes of one part.

This given graph has $5$ nodes, and the splitting made here is best because all nodes have even number of edges in the same part.

My idea was to do BFS over the nodes and when we find node with odd number of edges to put one node in the other part, but I can't come up with some strong idea.

Answer 1

By induction , we can prove that a partition exists with all nodes having even degree within the partition.
If all vertices have even degree , then we are done (Just partition it into the whole graph and an empty graph)
Otherwise let $v$ be a node with odd degree , now modify the graph by inverting the neighbourhood of $v$ (If $a$ and $b$ are neighbours of $v$ , then if they have an edge , remove it otherwise add it) and also remove $v $ from the graph , for the new graph , split it into 2 parts $A$ and $B$ such that all nodes in $A$ and $B$ have even degree , add $v$ back to $A$ if $A$ has even neighbours of $v$ , else add it to $B$. This works because in $A$(Or $B$ if we added $v$ to $B$) all degrees are even except for neighbours of $v$ which become even after adding $v$