📂Graph Theory

Hamiltonian Graph

Definition ¹

Let $G$ be a connected graph.

If there exists a closed path that includes all vertices of $G$, then $G$ is called a Hamiltonian graph, and that cycle is called a Hamiltonian cycle. If there exists a path that includes all vertices but is not closed, then $G$ is called a semi-Hamiltonian graph.

Explanation

Just as Eulerian graphs are interested in trails that pass through all edges, Hamiltonian graphs are interested in paths that pass through all vertices. Eulerian and Hamiltonian graphs do not have a logical relationship with each other. For example, the following graphs represent, in order, a graph that is Hamiltonian but not Eulerian, a graph that is both Hamiltonian and Eulerian, and a graph that is Eulerian but not Hamiltonian:

At first glance, it might seem easier since it’s not necessary to pass through all edges, but it becomes more complicated because each vertex can only be passed once. Thus, while Eulerian graphs have neatly provided equivalence conditions through their degrees, Hamiltonian graphs do not.

However, there is a theorem that guarantees a graph is Hamiltonian if it has sufficiently many edges. This is commonly known as Dirac’s Theorem. Dirac’s theorem became a corollary of Ore’s theorem with a simpler proof by Ore in 1960, after being proven in 1952, but it is still often called Dirac’s theorem.

See Also

• Graphs that have a closed trail including all edges: Eulerian graphs