**Hamiltonian cycles and Hamiltonian paths**

A *Hamiltonian path* is a path that visits every vertex once and only once,
except that it might (or might not) begin and end at the same vertex.

Hamiltonian path |

A *Hamiltonian cycle* is a Hamiltonian path that begins and ends on the same vertex and visits all the other
vertices in the graph exactly once. A Hamiltonian cycle does not necessarily traverse
every edge in the graph.

Hamiltonian cycle |

A graph is called *Hamiltonian* if it contains a Hamiltonian cycle.

The term *Hamiltonian* is derived from the name of the Irish mathematician William Rowan Hamilton who designed and marketed a puzzle whose solution
essentially required finding a Hamiltonian cycle in a graph.

On the surface, a Hamiltonian cycle may seem to be very much like an Eulerian circuit, but they are actually quite different. A graph that has an Eulerian circuit may or may not also contain a Hamiltonian cycle, and vice versa.

One well-known problem involving Hamiltonian cycles is the problem of finding a minimal Hamiltonian cycle in a weighted graph. this problem is also known as the *Traveling Salesperson Problem* or *TSP* because a solution to this problem answers a question commonly asked by traveling salespeople: What is the most efficient route that I can take to visit all of my clients?

Copyright © 1999-2000 SciMathMN