# 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.

## Identification of Hamiltonian Graphs

• 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.

## Applications of Hamiltonian Graphs

• 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

• 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.

## Examples

• 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.