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.

Graph

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.

  • Are empty sets of nodes allowed? – xskxzr Aug 10 at 8:13
  • I think brute force solutions like breadth-first search will be infeasible because in a graph with 200 nodes there are 2^199 possible (non-symmetric) groupings. – Auberon Aug 10 at 8:49
  • Yes, empty set of nodes is allowed, but note that the other set will contain all of the nodes, I was thinking about some fast bfs not the one trying all possible splittings. – someone12321 Aug 10 at 9:34
up vote 2 down vote accepted

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$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.