Ore's Theorem - Algorithm

Algorithm

Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.

1. Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
2. While the cycle contains two consecutive vertices v_i and v_{i + 1} that are not adjacent in the graph, perform the following two steps:
   • Search for an index j such that the four vertices v_i, v_{i + 1}, v_j, and v_{j + 1} are all distinct and such that the graph contains edges from v_i to v_j and from v_{j + 1} to v_{i + 1}
   • Reverse the part of the cycle between v_{i + 1} and v_j (inclusive).

Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether v_j and v_{j + 1} are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph. By an argument similar to the one in the proof of the theorem, the desired index j must exist, or else the nonadjacent vertices v_i and v_{i + 1} would have too small a total degree. Finding i and j, and reversing part of the cycle, can all be accomplished in time O(n). Therefore, the total time for the algorithm is O(n2), matching the number of edges in the input graph.