Finding Hamilton Paths and Circuits

The applet let's you create graphs and practice finding Hamilton paths and circuits.

Create Graph Tab

The edges of the graph are created by dragging the mouse. The vertices are created as needed. For example, if you start or stop the dragging in a vicinity of an existing node, the new edge becomes attached to this vertex. Otherwise, a new vertex is created.

You can always remove the last of your creations (Undo Last) or the entire graph (Reset) and start anew. When ready, move to the Practice Finding Hamilton Paths and Circuits tab.

Practice Finding Hamilton Paths and Circuits

There is no definite algorithm for finding the Hamilton paths or circuits. Start with selecting a vertex and continue to an adjacent node that has not been visited yet (except for the very last leg of the journey when you may close a Hamilton circuit.) In most cases this simple prescription will work just fine. In the situations where you can't continue to as yet not visited vertex you may retrace your steps by clicking on the Undo Last button at the lower right corner of the applet. Also, you can always start anew after pressing the Reset button.

When all the vertices of the graph have been traversed you'll see a message in red acknowledging this fact. At this point you have a Hamilton path. If it is possible to connect the last and the first vertices of the path, do that. This will produce a Hamilton circuit.