A basic question about approximation algorithms for the Traveling Salesman Problem Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard.  The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be decided.  This standard proof is discussed in many places including accepted answers on cs.stackexchange here and here.

Briefly, the standard proof for $k=2$ works as follows.  Suppose a graph $G$ with $n$ vertices is given as input to the Hamilton Cycle problem.  We create a weighted complete graph $H$ with the same $n$ vertices as follows: The edges in $G$ are given weight 1, and the added edges are given a large weight, say $n+2$.  Notice that every Hamilton cycle in $H$ either has total weight $n$, or at least $(n-1) + (n+2) = 2n+1$.  This gap allows a 2-approximation algorithm for TSP to answer the decision problem.  More specifically, if $G$ has a Hamilton Cycle, then the 2-approximation algorithm must return the value $n$ since the other Hamilton cycles have total weight $&gt;= 2n+1$.  On the other hand, if $G$ does not have a Hamilton cycle, then the 2-approximation algorithm will return a value larger than $n$.

I'm uncertain about something even more basic.  What would a 2-approximation algorithm return if we did not add the edges of weight $2n+1$?  In other words, suppose we take graph $G$ and create a weighted graph $G_1$ by assigning weight 1 to each edge in $G$, and we do not add any new edges.  In this case, the Hamilton cycles in $G_1$ (if any) all have total weight $n$, and they all correspond to Hamilton cycles in $G$.  There is no gap in the total weights of the Hamilton cycles.

What exactly would the 2-approximation algorithm return if $G$ has a Hamilton cycle?  And what if $G$ does not have a Hamilton cycle?
The misunderstanding comes from two variations of the TSP problem:


The input graph is complete.
The input graph is arbitrary.


The standard proof above must assume the first variation of TSP.  Thus, there is no k-approximation algorithm for the first variation unless $P=NP$.  The same result then follows for the second variation due to the fact that the second variation generalizes the first variation.

To answer the question directly: The input to the TSP variation in question must be a complete graph.

Note: The Wikipedia article states the following: Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge).  If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.