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.


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