trails. Sets that may satisfy for some tour may thus be found by enumerating closed alternating trails in , even if not every closed alternating trail makes into a tour; it could alternatively turn out to be a disconnected -regular subgraph. Key idea Alternating trails (closed or open) are built by extending a shorter alternating trail, so when exploring the neighbourhood of the current tour , one is exploring a search tree of alternating trails. The key idea of the Lin–Kernighan algorithm is to remove from this tree all alternating trails which have gain . This does not prevent finding every closed trail with positive gain, thanks to the following lemma. Lemma. If are numbers such that , then there is a cyclic permutation of these numbers such that all partial sums are positive as well, i.e., there is some such that for all . For a closed alternating trail , one may define if and if ; the sum is then the gain . Here the lemma implies that there for every closed alternating trail with positive gain exists at least one starting vertex for which all the gains of the partial trails are positive as well, so will be found when the search explores the branch of alternating trails starting at . (Prior to that the search may have considered other subtrails of starting at other vertices but backed out because some subtrail failed the positive gain constraint.) Reducing the number of branches to explore translates directly to a reduction in runtime, and the sooner a branch can be pruned, the better. This yields the following algorithm for finding all closed, positive gain alternating trails in the graph. State: a stack of triples , where is a vertex, is the current number of edges in the trail, and is the current trail gain. For all , push onto the stack. While the stack is nonempty: Pop off the stack and let . The current alternating trail is now . If is even then: For each such that (there are at most two of these), push onto the stack. If instead is odd then: If then report as a closed alternating trail with gain . For each such that and (there may be of these, or there could be none), push onto the stack. Stop As an enumeration algorithm this is slightly flawed, because it may report the same