Hamilton circuits

Definition

A Hamilton circuit is a path in a graph that visits each vertex exactly once and returns to the starting vertex. It differs from an Euler circuit, which traverses each edge exactly once.

5 Must Know Facts For Your Next Test

1. A Hamilton circuit must visit every vertex in the graph exactly once before returning to the starting point.
2. Hamilton circuits are named after the Irish mathematician Sir William Rowan Hamilton.
3. Determining whether a given graph contains a Hamilton circuit is an NP-complete problem, meaning it is computationally challenging.
4. A complete graph with n vertices always has a Hamilton circuit if n > 2.
5. Not all graphs have Hamilton circuits; for example, trees (connected acyclic graphs) do not contain any Hamilton circuits.

Review Questions

• What is the main difference between a Hamilton circuit and an Euler circuit?
• Can a tree have a Hamilton circuit? Why or why not?
• Is finding a Hamilton circuit in a general graph computationally easy or hard?

Related terms

Graph Theory:

The study of graphs, which are mathematical structures used to model pairwise relations between objects.

Euler Circuit: A path in a graph that traverses every edge exactly once and returns to the starting vertex.

Complete Graph:

A type of graph where there is an edge between every pair of vertices.