# Correctness of splitting an undirected tree into a forest of trees with even number of children

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:

1. Choose any node as a root node;
2. Recursively traverse a tree using depth-first approach;
3. 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):

1. Why starting DFS from any chosen root gives correct maximum number of removed edges?
2. 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
|
x


In (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:

1. What if it depends where you start cutting sub-trees?
2. 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.

• You're looking for a maximum matching, no? – Pål GD Mar 22 '15 at 13:43
• @PålGD Not exactly. Take a look at my comments below. – uintptr_t Mar 22 '15 at 18:18

• Removing an "even" edge deletes an even number of nodes. For other each edge $e$ in the tree these deleted nodes can only be at one side of the edge $e$. Thus it will not change evenness of $e$. – Hendrik Jan Mar 22 '15 at 12:35