It is known that tour expansion is a rather poor heuristic for generating short Hamilton cycles even in the planar Euclidean case. That comes as a surprise when learning of that for the first time.
The surprise is due to the fact that the heuristic seems to resemble complete induction if one starts with the convex hull of the pointset as the base case and then inserts as the next point the one that incurs the least length-increase of the tour:
base case:
- the relative order of the points on the convex hull is the same as in the shortest tour through all points.
induction step:
- if the the tour $T_n$ through the first $\left|CH\right|+n$ points is optimal, then the shortest tour $T_{n+1}$ through one additional point is again optimal ($\left|CH\right|$ shall be the number of points on the convex hull and $n\geq 0)$.
Question:
What are the reasons that prove that greedy tour expansion is not a variant of complete induction?
What I am looking for is a proof that clearly indicates, which of the conditions for the applicability of complete induction are violated by greedy tour expansion.