Xavier Holt edited Monotonicity_TSP_See_ref_fig__.md  almost 8 years ago

Commit id: 2f45dc35b141d91749a2b9126b51f19f7791432e

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 = \geq  |TSP(S'_{/p})|\). This proof holds for all  ## MST