---
abstract: |
    Recently, Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph metric (graph-TSP), which yielded a $\frac{4}{3}$-approximation guarantee on subcubic graphs as well as a substantial improvement over the $\frac{3}{2}$-approximation guarantee of Christofides’ algorithm on general graphs. The crux of their approach is to compute an upper bound on the minimum cost of a circulation in a particular network, $C(G,T)$, where $G$ is the input graph and $T$ is a carefully chosen spanning tree. The cost of this circulation is directly related to the number of edges in a tour output by their algorithm. Mucha subsequently improved the analysis of the circulation cost, proving that Mömke and Svensson’s algorithm for graph-TSP has an approximation ratio of at most $\frac{13}{9}$ on general graphs.

    This analysis of the circulation is local, and vertices with degree four and five can contribute the most to its cost. Thus, hypothetically, there could exist a subquartic graph (a graph with degree at most four at each vertex) for which Mucha’s analysis of the Mömke-Svensson algorithm is tight. We show that this is not the case and that Mömke and Svensson’s algorithm for graph-TSP has an approximation guarantee 