Christofides algorithm (by hand) I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:


[![enter image description here][1]][1]

Calculate minimum spanning tree T:


[![enter image description here][2]][2]

Calculate the set of vertices O with odd degree in T


Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O


(as all were odd, this should give us the original graph)
[![enter image description here][1]][1]

Construct a minimum-weight perfect matching M in this subgraph


(I am not sure if I did this right)
[![enter image description here][3]][3]

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph


[![enter image description here][4]][4]

This is definitely not right. 

What went wrong?
In fact, you have been correct all along. However, you have not finished Christofides algorithm yet.

The next step is "Calculate Euler tour".
In the last picture, you have obtained a multigraph all of whose vertices have even degrees. So it must have an Eulerian path. For example, let us select the Eulerian path A -> F -> A -> C -> B -> D -> E -> D -> A.

The last step is "Remove repeated vertices, giving the algorithm's output".
Removing the second A and the second D on that above path, we obtain a wanted output, A -> F -> C -> B -> D -> E -> A. Done.



Please note it is not very meaningful to apply Christofides algorithm on the given graph. 

"The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality". The given distances do not obey the triangle inequality, since d(B,D) + d(D, E) = 1 + 4 &lt; 6 = d(B,E). Moreover, the (direct) distance between A and B is not given, raising doubt whether this is a travelling salesman problem at all.