Table of contents |

2 History 3 See also 4 External links and resources 5 References |

## Definitions

In graph theory, a**Hamiltonian path**is a path that visits each vertex exactly once.

A **Hamiltonian cycle** (also called *Hamiltonian circuit*, *vertex tour* or *graph cycle*) is a cycle that visits each vertex exactly once.

A graph that contains a Hamiltonian cycle is called a **Hamiltonian graph**. Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to Hamiltonian cycle only if its endpoints are adjacent.

Similar notions may be defined for directed graphss, where edges (arcs) of a path or a cycle are required to point in the same direction, i.e., connected tail-to-head.

The **Hamiltonian cycle** or **Hamiltonian circuit problem** in graph theory is to find a Hamiltonian cycle in a given graph.

The **Hamiltonian path problem** is to find a Hamiltonian path in a given graph.

There is a simple relation between the two problems. The Hamiltonian cycle problem for graph **G** is equivalent to the Hamiltonian path problem in a graph **H** obtained from **G** by adding a new vertex and connecting it to all vertices of **G**.

Both problems are NP-complete. However, certain classes of graphs always contain Hamiltonian paths. For example, it is known that every tournament has an odd number of Hamiltonian paths.

The **Hamiltonian cycle** problem is a special case of the traveling salesman problem, obtained by setting the distance between two cities to unity if they are adjacent and infinity otherwise.

## History

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the *icosian game*, now also known as *Hamilton's puzzle*, which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the *icosian calculus*, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). Unfortunately, this solution does not generalize to arbitrary graphs.

## See also

## External links and resources

- Hamiltonian Page : Hamiltonian cycle and path problems, their generalizations and variations
- Weisstein, Eric W., Hamiltonian Circuit. Wolfram Research, 2003.

## References

- Rubin, Frank, "
*A Search Procedure for Hamilton Paths and Circuits'*". Journal of the ACM, Volume 21, Issue 4. October 1974. ISSN 0004-5411 - Nasu, Michiro, "
*A Study of Hamiltonian Circuit Problem*". fourth draft, April 4, 1996 - August 18, 1999 - DeLeon, Melissa, "
*A Study of Sufficient Conditions for Hamiltonian Cycles*". Department of Mathematics and Computer Science, Seton Hall University, South Orange, New Jersey, United States of America. [PDF] - Hamilton, William Rowan, "
*Memorandum respecting a new system of roots of unity*". Philosophical Magazine, 12 1856 - Hamilton, William Rowan, "
*Account of the Icosian Calculus*". Proceedings of the Royal Irish Academy, 6 1858