## 1-2 TSP

Let G be a complete undirected graph whose edge weights are all 1 or 2 (it is a special kind of metric).

Give a 4/3-approximation algorithm for Min Traveling Salesperson Problem (Min TSP) for this special case.

*Hint.* First find a 2-matching in G. A 2-matching is a subset M of the edges such that each vertex has exactly 2 edges incident on it. There is a polytime algorithm for this step (see https://cstheory.stackexchange.com/questions/8563/partition-a-graph-into-node-disjoint-cycles/8570#8570)