Monotonicity

TSP

See Figures \ref{fig:Aye} and \ref{fig:Bee}.

For all \(p\in S', \not\in S\):

• Let \(p_{i-1}, p_{i+1}\) be the points before and after \(p\) in our travelling-salesperson cycle.
• Let \(a,b\) be \(|p_{i-1}, p|, |p_{i+1}, p|\) respectively.
• Let \(c\) be \(|p_{i+1}, p_{i-1}|\).
• Let the segment of the cycle not involving any of these three points be defined \(L\).

If we remove \(p\) from our pointset S, we can always join \(p_{i-1},p_{i+1}\). We don't have to prove that this decision results in the optimal TSP for the reduced pointset, just that we 1) get a valid cycle and 2) never do worse that \(|TSP(S')|\).

1. This is pretty evident. All we do is remove the path \(p_{i-1}, p, p_{i+1}\) -- but we add an edge \(p_{i-1}, p_{i+1}\). Clearly besides not visiting \(p\) the architecture of our cycle doesn't change.
2. Let \(TSP^*\) indicate a valid but not necessarily minimum TSP cycle.
   • By the triangle inequality \(c \leq a + b\).
   • Therefore \(|TSP(S')| = |L|+a+b \leq |L| + c = |TSP^*(S'_{/p})|\).

This proof holds for all points \(\in S', \not\in S\) and works regardless of the order we remove them \(\square\).

MST

Adding additional points can give us a 'short-cut'. See \ref{fig:MST}.