String Reconstruction with Overlap Graph: Hamiltonian Paths

We now know that to solve the String Reconstruction Problem, we’re looking for a path in the overlap graph that visits every node exactly once. A path in a graph visiting every node once is called a Hamiltonian path, in honor of the Irish mathematician William Hamilton (see DETOUR: The Icosian Game). As this figureH_Path illustrates, a graph may have more than one Hamiltonian path.