Consider the following heuristic for building an approximate traveling$-$salesman tour $($cycle$),$ assuming that the edge weights satisfy the triangle inequality. Begin with a trivial cycle con$-$sisting of a singe arbitrarily chosen vertex. At each step, identify the vertex u that is not yet on the cycle but whose distance to any vertex on the cycle is minimum $($that is$,$ if C is the current cycle, for every vertex w $$ C compute the number d$($w$)=$ minv in C dist$($w$,$ v$)$ and choose the vertex u for which d$($u$)$ is minimum$).$ Suppose that the vertex on the cycle that is nearest to u is vertex v$.$ Extend the cycle to include u by inserting u just after v$.$ Repeat until all vertices are on the cycle.

Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.