Content: The Christofides algorithm finds a minimum spanning tree, then finds all the odd degree vertices, and adds extra edges using a minimum weight bipartite matching on those odd vertices to make all of them even, so that a Eulerian tour can be found (since all vertices are even now).
My question arises from a simple example: suppose there are four odd-degree vertices in the MST, labeled $v_1, ..., v_4$. Now suppose that $v_3$ and $v_4$ are already connected in the original MST, and further suppose that the minimum weight matching requires them to be connected. This means that the matching is redundant, and the two vertices still have odd degree at the end.
Does this simply mean that the bipartite matching has to be re-run to find the "next-to-minimum" matching, or are there other heuristics?