I know that part of the algorithm is to find a perfect matching for the set of vertices in $O$, which contains the odd vertices from the minimum spanning tree $T$ of the graph under consideration.
My question is, how do we know that a perfect matching exists in $O$? I know that an even number of vertices is a necessary condition for a perfect matching to exist, so we have that a perfect matching could exist, but what other characteristics ensure that it definitely exists?
I know that if a graph is regular bipartite then this implies that a perfect matching exists; but does $O$ always satisfy this condition? How do we view the set $O$ in terms of a graph - are the vertices isolated, do we view the vertices in a complete graph?
For context, I'm trying to demonstrate the algorithm for a graph with 9 vertices, 6 of them odd. I hence find a perfect matching for the 6 odd vertices (which I already have), but how can I be sure that one exists? Hope this is clear
The number of odd-degree vertices is guaranteed to be even: $2k$ for some $k$. We are looking for a perfect matching in the complete graph on those $2k$ vertices. So it's not a question of whether one exists: any way to partition the vertices into $k$ pairs is valid. However, we want this perfect matching to be a minimum-cost perfect matching (with respect to the costs from the TSP instance we're solving).
In general, for the traveling salesman problem, we assume that our host graph is a complete graph: every edge exists, but at what cost? If we want to model a problem where some edges don't exist, then we give those edges cost $\infty$ instead. However, the Christofides algorithm is only appropriate for the metric TSP, where - broadly speaking - this doesn't make sense.
(More precisely, costs of $\infty$ can only obey the triangle inequality if the graph of finite-cost edges is not even connected. In such a case, our minimum-cost perfect matching would have cost $\infty$, but that's okay, because in such a case, there's no TSP solution with a finite cost, either.)