Both the optimal tour though 30 Euclidean points and a perfect matching constructed by removing every other edge, are displayed below:
Is the matching minimal? If not, why not?
What operation is performed to the matching to shorten it, assuming this is possible? I understand one must construct an augmenting path though the points which misses some of the matching's edges, but why is such a path likely to exist? Or is it unlikely to exist?