Xavier Holt edited Monotonicity_TSP_See_ref_fig__.md  almost 8 years ago

Commit id: 4bc774ad2056b4d4338c0470249296e9b802b640

deletions | additions      

       

* Let \(c\) be \(d(p_{i+1}, p_{i-1})\).  * Let the length of the cycle of all points besides these three be defined as \(L\).  If we remove \(p\) from our pointset S, we can always join \(p_{i-1},p_{i+1}\) to make a new TS cycle.  By the triangle inequality \(c \leq a + b\). Therefore \(|TSP(S)| = L+a+b \leq L + c = |TSP(S_{/p})|\).  For all points |TSP(S_{/p})| \square\).  ## MST