Correctness of splitting an undirected tree into a forest of trees with even number of children
I got my "Aha! Gotcha" moment when I changed my point of view from nodes (as root of a subtree) to edges. Let me explain.

The set of edges that can be cut is a "static property", the set of choices is not changed by the earlier cuts that have been made. Any edge is considered to be "even" if on both sides it has an even number of nodes in the tree. Clearly we can only cut even edges. But also, cutting an even edge does not change the even property of the remaining edges, as we merely remove an even number of nodes in subtrees. 

So, we are set to find the even edges, and we will cut them all. The proposed solution uses DFS, but any decent traversal will do I would think. The property that a subtree has an even number of nodes now means (in my terminology above) that the edge outside leading to the root of the subtree is in fact even.