# Planar TSP: no node insertion?

Since planar TSP with n nodes is NP-hard, we cannot simply find an optimal solution with n-1 nodes and then insert the remaining node at one of the solution's edges to find the optimal solution of the original TSP problem. So, is there a planar graph with an optimal solution, such that when we add a certain extra node, the new graph's optimal solution has none of the edges of the previous optimal solution?

• When you say planar TSP, do you mean Euclidean TSP? I.e. a set of points in $\mathbb{R}^2$ with Euclidean distances? – G. Bach Nov 9 '15 at 20:57
• yesm that's what I mean. – Albert Hendriks Nov 17 '15 at 10:42