Minimum spanning subgraph of even degree
I just realised that example A is an instance of the Travelling Salesman Problem, which is NP-hard. So the best we can hope for is an approximation algorithm.

I also realised that this is problem is an instance of b-matching, where you want to select up to b edges incident on each node of minimal total weight. Here we have the additional constraint that b is even. I found a couple of papers that solve b-matching:

http://www.aporc.org/LNOR/10/ISORA2009F12.pdf
http://proceedings.mlr.press/v15/huang11a/huang11a.pdf