# Graphs and Networks: Hamiltonian Graphs

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