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 consisting of a single 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

otin C compute the number d$($w$)=\backslash$text$\{$min$\}\_\{$v$\backslash$in C$\}\backslash$text$\{$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.