Mathematics — Graph Theory · spanning-subgraph-odd-degree
Problem
Let G be a connected multigraph with an even number of vertices. Prove that there exists a spanning subgraph H of G such that each vertex of H has odd degree (in H).
[Hint: One way to solve this begins by reducing the problem to the case when G is a tree.]