Decompose a tree into forest

Question

How can I decompose a tree into forest such that each tree contains even number of vertices? Does i need to decompose tree randomly and check for every forest? I have already created adjacency matrix but doesn't helping me anyhow!
What should be the correct way to achieve the same?

Answer 1

The problem as stated is trivial. Just return the tree.

In order for every tree in a forest to contain an even number of vertices, the total vertices in the forest must be even. Which implies the number of vertices in the original tree is even. Since a tree is a forest, simply returning the tree is a valid solution.

Answer 2

One solution that comes to mind is to start at some root node, and do something like a BFS, stopping when you have a tree of a desired size. Then treat the next node you were going to visit in your BFS as the new "root" node, and repeat.