Finding a minimum weight perfect matching in Christofides TSP algorithm Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd vertices. N is even, so a bipartite matching is possible. 

When the N odd-degree vertices are found, there are $n \choose \frac{n}{2}$ possible ways to split them into two sets. Does Christofides' algorithm really need to run a min-weight bipartite matching for all of these possible partitions? Or is there a better way? 

I realize there is an approximate solution, which is to greedily match each vertex with another vertex that is closest to it. However, if the exact solution is to try all possible partitions, this seems inefficient.
There is the Blossom algorithm by Edmonds that determines a maximal matching for a weighted graph.