Step 4a of the original paper describing the Lin-Kernighan TSP algorithm states that the choice of edge $x_i = (t_{2i}, t_{2i+1})$ to be deleted is uniquely determined by the choice of edge $y_{i-1} = (t_{2i-1}, t_{2i})$ previously added. Helsgaun elaborates on this by saying:
"... only one of these makes it possible to ‘close’ the tour (by the addition of $y_i$). The other choice results in two disconnected subtours"
Can somebody explain why this is the case, and how to tell which choice of $x_i / t_{2i}$ given some $y_{2i-1}$ is correct?
I have an idea (that I'm not sure is correct) of a way to test if a tour contains disconnected subtours*, but doing so would force you to build a tour $T'$ from $T, X, Y$ at every step of a k-opt move, which is inefficient.
*if tour
is a list of cities containing a disconnected subtour then some city must be visited twice, so you could do something like len(set(tour)) == len(tour)
in python