I have the following problem, which I am struggling with. It asks to find the maximum number of edges to be removed from a tree to convert it to a forest, where every component will have an even number of vertices.
Note: The tree in the input will be such that it can always be decomposed into components containing even number of nodes.
You are given a tree (a simple connected graph with no cycles). You
have to remove as many edges from the tree as possible to obtain a
forest with the condition that : Each connected component of the
forest should contain an even number of vertices.
I tried to tackle the problem for a reasonable amount of time and can not find a way to solve it. Can someone explain me the solution, and also how to come up with this solution?
P.S. I am not looking for a code here. I need someone with the knowledge of graph theory to explain me the logic.
Best Answer
Suppose that the tree has $n$ vertices; clearly $n$ must be even. Consider an edge $e$. Removing $e$ breaks the tree into two subtrees; either both subtrees have an even number of edges, in which case I’ll call $e$ an even edge, or both have an odd number of edges, in which case I’ll call $e$ an odd edge.
If you remove an odd edge, the resulting subtrees have odd numbers of vertices, and any further removal of edges will leave you a forest in which at least two trees have odd numbers of vertices; thus, you must never remove an odd edge.
It’s not hard to see that if you remove an even edge, each of the remaining edges retains its original parity in its subtree: if it was even in the original tree, it’s still even in its subtree, and if it was odd in the original tree, it’s still odd in its subtree. Thus, the resulting forest has the same number of odd edges as the original tree and one fewer even edge.
As long as there’s an even edge in your forest, you can remove it without producing a tree with an odd number of vertices, so you simply want to remove all of the even edges. (This is what was done in the sample on the linked page: the two edges that were removed were precisely the two even edges in the original tree.)