Pairs of Adjacent Hamiltonian Circuits with Small Intersection

Consider the question: When can the edges in a pair of Hamiltonian circuits be redistributed to form another pair of circuits with the same union and intersection? A class of pairs is exhibited which intersect in two edges and cannot be rearranged in this way. A connection to algorithms for the traveling salesman problem is explained using the convex polytope of Hamiltonian circuits in . The exhibited pair is shown to be an edge of that polytope.