Let $G(V,E)$ be a complete symmetric graph without self-loops or parallel edges; depending on the context the edges may however be interpreted as a pair of antiparallel arcs of equal weight.

A *vertex disjoint cycle cover* is the set of arcs $\lbrace \left(i,\delta^{-1}(i)\right)\rbrace\subseteq E$ where $i$ denotes the vertex with label $i$ and $\delta^{-1}(i)$ is the vertex with the label that is mapped to *position* $i$ by a derangement $\delta$ of the vertex labels.

Questions:is it guaranteed that we will eventually encounter a Hamilton cycle if we repeatedly

- calculate a vertex disjoint cycle cover $C$ without pairs of antiparallel arcs of $G$
- delete from $G$ an edge $e$ that is randomly selected from $C$ among the edges such that $\,G\setminus e\,$ still contains a vertex disjoint cycle cover without pairs of antiparallel arcs.
In case we always do eventually encounter a Hamilton cycle:

what is known about the TSP heuristic of always deleting from $G$ the edge of the current lightest cycle cover the edges that meet the constraints of random selection and will yield the lightest vertex disjoint cycle cover in the next iteration?

Ruling out cycle covers with pairs of antiparallel arcs is essential because otherwise $K_4$ would be a counterexample: the arcs of perfect matching would be a cycle cover and after having deleted two edges one would be left with the edges of the third perfect matching.

encounterI do indeed mean that one of the generated vertex (disjoint) cycle covers will be a Hamilton cycle; I had in mind a human being that checks the sequence of generated vertex covers. The terminology for the generated subgraphs is very diverse; have also seen "cycle packing"; or "disjoint cycle cover"; I used "vertex disjoint cycle cover" following Bodo Manthey's terminology. Your ounter-example made clear that further constraints must be imposed on the edge that is deleted from the current vertex cycle cover $\endgroup$1more comment