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?