The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem.
Appendix 1: Artifact 627

Appendix to JAIR Article Vol 9, pp 219-245.

The following diagram illustrates the artifact that caused the difficulty on the 100 vertex graph from the experiments run on Gn* and discussed in Section 4.2. It occurred in graph number 627 of that experiment, and hence the name.

The red edges are forced to be in any Hamiltonian cycle because they are each incident on a vertex of degree two. If the blue edge is added to the current Hamiltonian cycle, then the black edges incident to the blue vertex on the right must all be pruned. This means the two green vertices become degree two, which means the other two edges incident to the blue vertex on the left must be pruned. This makes the left blue vertex degree one, which implies the Hamiltonian cycle cannot be completed.

On the other hand, if the blue edge is not part of a Hamiltonian cycle, then it must be deleted (e.g. when another edge is selected from the blue vertex on the right). But deleting the blue edge means the blue vertex on the left will be degree two, and the resulting pruning leaves three vertices of degree two as neighbors of the right blue vertex. Again no Hamiltonian cycle is possible.

Our current program cannot detect this artifact until it tries to extend the Hamiltonian path into it. If it is lucky enough to start on one of the forced (red colored) paths, then it immediately backs out and fails. If instead it starts far away, then it will repeatedly enter the artifact, back out, and enter again from a different path.

J. Culberson and B. Vandegriend, October 1998.