A simple graph theory example in the spirit of the question.

THM. Let $G$ be a connected graph with $2j$ vertices of odd degree. Then there are $j$ (open) eulerian trails whose endpoints are the vertices of odd degree.

PROOF. Add $j$ edges between the odd-degree vertices to make $G$ into a (multi-)graph with only even degrees. Choose an eulerian circuit, then remove the extra edges.