A 4/3 algorithm for TSP for a special case

Here is a special case that illustrates the main idea of the Moemke-Svensson algorithm (after receiving an email from Ola Svensson with comments). The result in that special case was already known (Boyd, Sitters, van der Ster, Stougie, IPCO 2011) but by different methods; the point of this post is to explain the deletion/addition/removable pairs idea.

Input: shortest path metric in a 2-edge-connected unweighted graph G in which every vertex has degree 3.
Output: 4/3 approximation to TSP

Algorithm:
1) Let T be any depth-first-search tree.
2) Define removable pairs as follows: each back edge goes into some vertex, call it v, and (if v is not the root) is paired with a tree edge from v to the child of v. ("the" child, because the graph is cubic).
3) Take M, a random perfect matching of G such that each edge is in M with probability 1/3 (known from some 1980's discrete math publications).
4) For each edge e of M that is in a removable pair, remove e from G. For each edge e of M that is not in a removable pair, add e to G, creating a duplicate edge.
5) Output an Eulerian tour of resulting multigraph.

Analysis of correctness: in the multigraph, every vertex has even degree, 2 or 4, and, given the definition of removable pairs, it is not hard to convince oneself that it is still connected, so it's Eulerian.

Analysis of cost: G has (3/2)n edges. T has n edges. (Almost) every back edge is in a removable pair, so there are (n/2) removable pairs, each pair with 2 edges, for a total of (n/2)*2=n removable edges. The other (n/2) edges are unremovable. The expected size of the output is:
(#edges of G)+(# unremovable)*prob(in M) - (# removable)*prob(in M)=(3/2)n+(n/2)*(1/3)-(n)*(1/3)=(4/3)n,
give or take a few.

This is so simple that it could probably be taught at the senior undergraduate level.

And that concludes my posts about TSP, for now.