# MSTs in Christofides Algorithm

I am implementing the Christofides algorithm for TSP problem and currently I have one issue with the MST result. Let's assume that I have one graph $G$, whereas I can get $MST_1$ and $MST_2$ where both are Minimum Spanning Trees, because $G$ contains more than one edge with the same weight.

In image [2] below, the difference between $MST_1$ and $MST_2$ is basically the $Arlington \to Somerville$ or $Arlington \to Belmont$ (or vice-versa) connection. Depending on the internal representation of the graph, whether a adjacency matrix or list, this could happen by just altering which node will be the first, e.g. if $Arlington$ will be processed earlier than $Somerville$.

The difference of dealing with one or the other, is the next steps of Christofides algorithm, that requires to apply the Minimum-Weight Perfect Matching algorithm on the odd nodes.

The $MST_1$ has only $4$ odd nodes and the perfect matching result is $Arlington \to Medford$ and $Cambridge \to Everett$, which I will call $MWPF_1$. The $MST_2$ has $6$ nodes and the perfect matching result is $Arlington \to Medford$, $Somerville \to Everett$ and $Belmont \to Cambridge$, which I will call $MWPF_2$.

The next step from Christofides is to merge both edges from $MST$ with the ones from perfect matching.

Now, if we choose to merge both $MST_1$ and $MWPF_1$, we will end up with nodes only with even degrees that's what we want as the next step is to calculate the Eulerian Circuit.

But, if we choose $MST_2$ and $MWPF_2$, we will end up with only one new edge, as other two are already present ($Somerville \to Everett$ and $Belmont \to Cambridge$) in $MST_2$. The result then will be $4$ odd vertices and no possible Eulerian Circuit can be generated out of this merge!

How this should be dealt in Christofides algorithm? Should all the $MSTs$ generated from one graph to be tried out?

So in your second case, you now have a multigraph where edges $(Somerville \rightarrow Everett)$ and $(Belmont \rightarrow Cambridge)$ each show up twice.