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