Hamiltonian graph

Definition

A connected graph with 3 vertices is Hamiltonian if it has a walk which visits every vertex exactly once and then returns to its starting point.

Since such a Hamiltonian walk never repeats vertices (except for returning), it can’t repeat edges either.

Note

This doesn’t imply that a Hamiltonian graph is definitely Eulerian, since a Eulerian circuit also require to visit all the edges

The vertices and edges involved in the walk form a cycle. Thus, a graph is Hamiltonian if and only if it contains a spanning cycle (where “spanning” means “using all the vertices”). In other word, is Hamiltonian if and only if you can delete some edges from and obtain a graph isomorphic to the cycle graph (where is the number of vertices in ).

Example

The following graph is Eulerian but not Hamiltonian (no way to only visit once)

Example

The graph of vertices and edges of a cube is Hamiltonian The same holds for the other regular polyhedra: tetrahedron, octahedron, dodecahedron, and icosahedron.

Below is a necessary condition for a graph to be Hamiltonian

Theorem

Let be a Hamiltonian graph

1. for any vertex of , the graph is connected
2. more generally, for any nonempty subset of the set of vertices of , the graph obtained by deleting all the vertices in and their edges has at most connected components

Subtopics

The Ore’s theorem states that a graph with sufficiently many edges must be Hamiltonian.

See Also

• Eulerian