# Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)

• $$\alpha$$ denotes the start and end vertex of the Eulerian path

## Step 3 - Form the subgraph of $$G$$ using only the vertices of $$O$$

This is starting to get confusing

## I am NOT satisfied

Did I do something wrong or did I simply just hit an sub-optimal solution. It is not hard to see that the Eulerian path easily could be improved by either connection $$G \rightarrow H$$ or $$A \rightarrow B$$ as illustrated underneath:

• Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution. – Yuval Filmus Nov 27 at 21:07
• @YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right? – Sebastian Nielsen Nov 27 at 21:46
• I’m not going to check your solution. I can help you with any conceptual difficulties. – Yuval Filmus Nov 27 at 21:49

On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$$\alpha$$ should be replaced by edge HG.