Type the three-step APPROX-TSP-TOUR (metric TSP)

Answer

T = MST-PRIM(G, c, r) H = preorder walk of T from r return cycle H

MST is the lower bound (c(T) ≤ c(H*)); the preorder walk shortcuts the doubled walk, and the triangle inequality guarantees the shortcut never costs more, giving c(H) ≤ 2c(H*).