finding a cycle cover for which they can upper bound the number of components. This general approach was also taken by Boyd et al. who combined it with polyhedral ideas to obtain approximation guarantees of $4/3$ for cubic graphs and $7/5$ for subcubic graphs, i.e. graphs with degree at most three at each vertex [@boyd2011tsp]. Shortly afterwards, Oveis Gharan et al. proved that a subtle modification of Christofides’ algorithm has an approximation guarantee of $3/2-\eps_0$ for graph-TSP on general graphs, where $\eps_0$ is a fixed constant with value approximately $10^{-12}$ [@gharan2011randomized].

Mömke and Svensson then presented a beautiful new approach for graph-TSP, which resulted in a substantial improvement over the $3/2$-approximation guarantee of Christofides [@DBLP:conf/focs/MomkeS11]. Their approach also lead to a surprisingly simple algorithm with an $4/3$-approximation guarantee for subcubic graphs. We will discuss their algorithm in more detail in Section \[sec:MS\], since our paper is directly based on their approach. Ultimately, they were able to prove an approximation guarantee of $1.461$ for graph-TSP. Mucha subsequently gave an improved analysis, thereby proving that Mömke and Svensson’s algorithm for graph-TSP actually has an approximation ratio of at most $13/9$ [@DBLP:conf/stacs/Mucha12]. §and Vygen introduced an approach for graph-TSP based on ear decompositions 