Is there a technique to find a hamilton circuit in a graph?

Question

My textbook goes in depth about how to show that a graph does NOT have a hamilton circuit, but one of its practice problems asks you to find a hamilton circuit in a graph that does have a hamilton circuit. My question is there a theorem/way I can easily identify a hamilton circuit in a graph without trial and error (I.E. trying to just find a hamilton circuit by picking and connecting random vertices)?

Answer 1

This is a hard computational problem in general, and so I can't give you a universal technique that always solves the problem quickly. But here are some tips that can help you with small cases that are easy to solve by hand.

• If a vertex has only $2$ usable edges coming out of it, then both of those edges have to be part of the Hamiltonian cycle.
• If we've already selected $2$ edges out of a vertex, then none of the other edges out of that vertex can be in the cycle, and should be marked as not usable.
• If adding an edge would create a short cycle that includes only some, but not all of the vertices, then that edge can't be part of the Hamiltonian cycle, and should be marked as not usable.
• Generalizing the first bullet point: if there is a set of vertices $S$ with only two usable edges between $S$ and the rest of the graph, then both of those edges have to be part of the Hamiltonian cycle. (Also, an even number of the edges between $S$ and the rest of the graph are used, so if you've figured out what happens for all but one of the edges, the last edge is either definitely in or definitely out.)

Applying these steps over and over again will sometimes get you to a Hamiltonian cycle. You might also have to do some casework: when none of these steps apply, pick an edge that looks promising, and add it to the cycle (maybe switching to a different color to mark things in). Then, keep making the deductions above and see if you get a Hamiltonian cycle or a contradiction.

If you have to do too much of that, that's the point at which you decide the graph is too complicated to find a Hamiltonian cycle in it by hand.