# FindHamiltonianCycle is not invariant to edge permutation

Bug introduced in 9.0.1 or earlier and fixed in 10.0

Found this bug-like behaviour today: if the order of edges is changed so that VertexList does not return the vertices in canonical order, FindHamiltonianCycle is not always able to find the Hamiltonian cycle, that is obviously there.

edges = {1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1};
g1 = Graph[edges, VertexLabels -> "Name", ImagePadding -> 10];
g2 = Graph[RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];

{g1, FindHamiltonianCycle[g1, All], VertexList@g1}
{g2, FindHamiltonianCycle[g2, All], VertexList@g2}


If a vertex list is specified, that might help, but not always:

g3 = Graph[{1, 4, 2, 3}, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];
g4 = Graph[{4, 1, 3, 2}, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];

{g3, FindHamiltonianCycle[g3, All], VertexList@g3}
{g4, FindHamiltonianCycle[g4, All], VertexList@g4}


Is this a bug? If so, at least it is consistent with HamiltonianGraphQ:

HamiltonianGraphQ /@ {g1, g2, g3, g4} ==> {True, False, True, False}


Mathematica 9.0.1, Windows 7, x64.

• It seems to work OK if you also specify the vertex set: g2 = Graph[Range@4, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];{g2, FindHamiltonianCycle[g2, All], VertexList@g2} Sep 8 '13 at 18:58
• @belisarius As you can see in my g3 and g4 examples, that is not always true. Surely, if the vertex list and the edge list comply in some undocumented sense (even if it is simply canonical ordering) it works, I think it is unwanted behaviour. Waiting for TechSupport at the moment... Sep 8 '13 at 20:50
• You should probably report it to support. Sep 12 '13 at 15:24
• @Szabolcs I did, with several other issues still in the pipeline, but the TechSupport web interface is broken (throws error when submitted), and they were unable to help me via the chat. No reply to emails yet. Perhaps someone knows what is going on at WRI support...? Sep 12 '13 at 15:27
• I tagged this as a bug. According to the docs, FindHamiltonianCycle only returns {} if no such cycle exists. Unfortunately I couldn't get the Combinatorica version to work on directed graphs. Did you receive a reply from support? Sep 16 '13 at 17:04

1. Supply correctly sorted vertex names with Graph (as in Graph[{1, 2, 3, 4}, ...]). Since we don't know what is the required vertex order (might not be standard sorting), this is not sure to succeed.
2. Undirect the graph using UndirectedGraph and check for Hamiltonian cycles in the undirected graph. If it finds any, convert UndirectedEdge-s to DirectedEdges in the found cycles, and check for all found cycle whether the original directed graph contains