Graphs and Networks: Hamiltonian Graphs

Basic Concept

A Hamiltonian graph is a graph that has a Hamiltonian circuit.
A Hamiltonian circuit (or Hamiltonian cycle) is a path in a graph that visits each vertex exactly once before returning to its starting vertex.
Hamiltonian circuits are named after the Irish mathematician Sir William Rowan Hamilton, who first defined them.
There’s a huge difference between a graph having a Hamiltonian circuit and finding that circuit. While the former is easy, the latter is considered to be a difficult computational problem known as the Hamiltonian cycle problem.

Unfortunately, unlike Eulerian graphs, there are no definitive criteria to quickly identify Hamiltonian graphs.
The best known criterion is named after the mathematicians G.A. Dirac and Claude Berge. It states that a graph with n vertices (n≥3) is Hamiltonian if every vertex has degree n/2 or greater.
A degree of a vertex, in this case, is the number of edges connecting it to the rest of the graph.

The most well-known application of Hamiltonian circuits is the travelling salesman problem. The goal of this problem is to find the shortest possible circuit that visits each city on a map once and only once, before returning to the starting point.
They are also critical in the design of electronic circuits, optimisation problems, and the development of efficient algorithms in computer science.

The Hamiltonian cycle problem is a topic of intense study in computational mathematics and computer science.
It is known as an NP-complete problem, which means that it is one of a group of problems for which no fast solution algorithm is known.
The problem is particularly interesting because if a fast solution was found, it would automatically mean that fast solutions exist for a vast number of important problems in areas including operations research, computer science, and logistics.

The simplest Hamiltonian graph is a cycle graph with 3 or more vertices. This simply means that if you draw a shape and connect all vertices without crossing any lines, you have a Hamiltonian cycle.
Another simple example of a Hamiltonian graph is a complete graph with more than 2 vertices. Here, every vertex is directly connected to every other vertex.
The Dodecahedron is Hamiltonian: one can visit every node on the shape exactly once and return to the start without retracing any edge.