Which of the following statements are true for the given special cases of the Traveling Salesman Problem? I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:


  Which of the following statements is true?
  
  
  Consider a TSP instance in which every edge cost is either 1 or 2. Then an optimal tour can be computed in polynomial time.
  Consider a TSP instance in which every edge cost is negative. The dynamic programming algorithm covered in the video lectures might not
  correctly compute the optimal (i.e., minimum sum of edge lengths) tour
  of this instance.
  Consider a TSP instance in which every edge cost is negative. Deleting a vertex and all of its incident edges cannot increase the
  cost of the optimal (i.e., minimum sum of edge lengths) tour.
  Consider a TSP instance in which every edge cost is the Euclidean distance between two points in the place (just like in Programming
  Assignment #5). Deleting a vertex and all of its incident edges cannot
  increase the cost of the optimal (i.e., minimum sum of edge lengths)
  tour.
  


I argue as follows:

The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.

If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.

Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex v, skip straight from v's predecessor to its successor on the tour. Because Euclidean distance satisfies the "Triangle Inequality", this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.

However, I'm not able to find any significance for TSP problems with unit edge costs. Is option 1 merely a trick, or is there more to it?
Statement 1 is false (assuming P $\neq$ NP) because any instance $G$ of the NP-complete Hamiltonian Cycle problem can be reduced to an instance of the TSP in which every edge cost is either 1 or 2. 

Why? Define a TSP instance on a complete graph $K_n$, with edge cost 1 whenever the corresponding edge is also in the original graph $G$, and edge cost 2 otherwise. Now a TSP tour of cost $\le n$ exists in the complete graph if and only if $G$ has an Hamiltonian cycle.