Consider the following naive algorithm for finding Hamiltonian cycles on a simple undirected graph G with n vertices:
- Choose an arbitrary vertex and mark it as vertex 1
- Choose an arbitrary unmarked neighbor of vertex 1, move to it, and mark it as vertex 2
- Repeat step (2) while the current iteration i < n and vertex i has unmarked neighbors
- If vertex n is adjacent to vertex 1, move to vertex 1 and terminate
It seems pretty intuitive to me that this algorithm fails to find Hamiltonian cycles most of the time on most graphs. However, there are some graphs for which this algorithm will always produce a Hamiltonian cycle, no matter where it starts or which subsequent vertices it chooses. As far as I'm aware, these graphs are: (1) a cycle on n vertices, (2) a complete bipartite graph on n vertices where the partite sets have the same magnitude, and (3) the complete graph on n vertices. I could be overlooking something, but I think it's trivial to show this. But for every graph other than these three types of graphs, I'm pretty sure there is at least one instance where the algorithm fails. The thing is I'm having a lot of trouble explicitly showing this.
I tried breaking the cases up into non-regular and regular graphs (not including the 3 mentioned above), but I'm struggling to show the non-regular case, let alone the regular case. My general approach is to consider a graph G that has at least one Hamiltonian cycle, but isn't one of those three graphs and then somehow manipulate that cycle to construct a "failed attempt" for the algorithm. Needless to say, it isn't working out. I think there might be some form of combinatorial argument, but I don't really know how to start going about finding it, since G can be almost any simple undirected graph. All of the theorems I looked at aren't of much help because they are about the existence of a hamiltonian cycle, but I'm looking for (vaguely) for the lack of one. So at this point, I'm stuck.
So to summarize my question: how can one explicitly show that for any graph that isn't one of the three graphs listed above, the algorithm has a non zero probability of failure?
Best Answer
The paper "Randomly Traceable Graphs" by Gary Chartrand and Hudson V. Kronk tackles this question, and confirms that the three types of graph ($C_n$, $K_n$, $K_{m,m}$) are the only ones:
https://epubs.siam.org/doi/abs/10.1137/0116056
Randomly Traceble graphs are graphs where every random self-avoiding path eventually visits all vertices (i.e. becomes a Hamiltonian path).
Randomly Hamiltonian graphs are Randomly Traceble graphs where every one of those random Hamiltonian paths can be closed to become a Hamiltonian cycle.
The paper first proves that all Randomly Traceble graphs with $n\ge3$ are randomly Hamiltonian. This is simple: Given any randomly traceable graph with a Hamiltonian path $v_1$, $v_2$, ..., $v_n$. The path $v_2$, ..., $v_n$, must be extendable to a Hamiltonian path since the graph is Randomly Traceable. Therefore $v_n$ and $v_1$ are connected by an edge, and any Hamiltonian path can be closed to become a Hamiltonian cycle. In the rest of the paper this trick of proving an edge must be present by constructing a hamiltonian path between its two vertices is repeatedly used.
The paper then views any Randomly Traceable graph as an outer (Hamiltonian) n-cycle possibly with diagonals.
If it has no diagonals, then it is just a cycle graph $C_n$.
If it has triangles (formed by two outer edges and one diagonal) then it turns out that all diagonals must be present and it is a complete graph $K_n$.
If instead it has 4-cycles (formed by three outer edges and one diagonal) then it turns out that it must be $K_{n/2,n/2}$ with $n$ even.
If it has larger cycles, then it will also have triangles, so no other types of randomly Hamiltonian graphs exist.