This problem is easier than rating should be if you know the trick.

Invariant: graph G is decomposable if and only if all the connected components of G has even number of edges.

A tree is very easy to be decomposed. Creating a tree equivalent to each connected component will lead to the answer.

Hope this help, Mick :)

It helped me a lot, thank you!
I read a proof of the fact that any connected graph with even number of edges is decomposable, but it was quite complicated and didn't allude at any good algorithm underneath.
Your idea is much simpler and easier to proof