Given an undirected tree (i.e. a tree without any designated root) of even number of nodes.The task is to remove as many edges from the tree as possible to obtain a forest of trees,where each such tree contains even number of nodes.And return/output number of removed edges as an output/answer.Counting maximum number of removed edges is relatively simple:Choose any node as a root node;Recursively traverse a tree using depth-first approach;Count number of children of each sub-tree (from bottom to up), and cut sub-tree from the tree if this sub-tree has even number of children (i.e. simply increment counter of removed edges);This solution is correct but I don't understand why.I would like to see proof of correctness of such algorithm.In particular, I have the following doubts (when I'm thinking on this solution):Why starting DFS from any chosen root gives correct maximum number of removed edges?Why cutting sub-trees with even number of children from bottom to up gives correct result?I wrote on paper all possible configurations 1, 2, 3, 4, 5, 6-nodes of undirected trees.For example, there are two possible configurations of undirected tree with 4 nodes:(a)x-x-x-x(b)x-x-x  |  xIn (a), you can split a tree into 2 sub-trees with 2 nodes each.In (b), you can not do it since it will be two sub-trees of odd number of nodes (with 1 node and with 3 nodes respectively).So my doubts based on suggestions:What if it depends where you start cutting sub-trees?What if greedy cutting sub-trees with even number of children from bottom to up doesn't give correct maximum number of removed edges? (continue of first question)This puzzle is described on HackerRank as Even Tree.Their editorial and discussion just declared algorithm but they don't say why it works.Also, I found discussion on stackoverflow but they also don't give explanation why such approach works.
Correctness of splitting an undirected tree into a forest of trees with even number of children
algorithms;trees;graph traversal
I got my Aha! Gotcha moment when I changed my point of view from nodes (as root of a subtree) to edges. Let me explain.The set of edges that can be cut is a static property, the set of choices is not changed by the earlier cuts that have been made. Any edge is considered to be even if on both sides it has an even number of nodes in the tree. Clearly we can only cut even edges. But also, cutting an even edge does not change the even property of the remaining edges, as we merely remove an even number of nodes in subtrees. So, we are set to find the even edges, and we will cut them all. The proposed solution uses DFS, but any decent traversal will do I would think. The property that a subtree has an even number of nodes now means (in my terminology above) that the edge outside leading to the root of the subtree is in fact even.