Hamiltonian Graph: Path and Cycle Explained

When you’ve worked with graphs in computer science, you might have come across the term Hamiltonian graph. Simply put, a Hamiltonian graph is one that contains a Hamiltonian path. This path visits each vertex exactly once. When this path starts and ends at the same vertex, then it is a Hamiltonian cycle. Such graphs are not just theoretical, they have practical applications like optimizing delivery routes or sequencing genomes. In this blog post, you will learn what a Hamiltonian graph is, as well as find out some of the important properties and applications of Hamiltonian graphs, and also (using the simple code in C++), you will be able to check whether your graph is Hamiltonian or not.

Table of Contents:

What Makes a Graph Hamiltonian

A graph must have a Hamiltonian path to be considered a Hamiltonian graph. Consider a situation where you are moving to a city and you do not want to miss a single location there (node), and you do not want to repeat the locations. In case such a path exists, it is a Hamiltonian path. Now, if you have a path of visiting all the rest of the locations exactly once, after which you are able to reach your original location, you have got yourself a Hamiltonian cycle. It’s important to note that not all edges need to be part of the cycle; as long as there exists one Hamiltonian cycle, the graph is Hamiltonian.

A Hamiltonian graph is just a graph that has such a cycle. The graph connects all nodes in such a way that you can start at any vertex, visit all of the rest once, and then get back to the beginning.

As a concrete example, suppose a graph has 5 vertices, and you can trace a path such as 0→1→2→4→3→0 that would mean that it has a Hamiltonian cycle, and the graph is Hamiltonian.

The graphs are also very interesting since determining whether a graph is Hamiltonian or not is not as simple as verifying that it is connected. Instead, there is no general rule, and the procedure can become intricate very fast. This explains why the knowledge of their structure is the most helpful in order to solve problems effectively.

Key Properties of Hamiltonian Graphs

When you decide to work with Hamiltonian graphs, there are some properties that will help you decide if the path in the graph is truly a Hamiltonian cycle or not. There is definitely no singular rule to determine, but a few theorems give us specific clues.

1. Dirac’s Theorem

Suppose a graph has N vertices in total, where N is more than or equal to 3, and each of the N vertices is connected to at least N/2 other vertices, then the graph is guaranteed to be Hamiltonian.

Example:

In the case of a graph with 6 vertices, each of the vertices needs to connect with at least 3 others. In the case that this is true of every vertex in the graph, then there is a probability that the graph will be Hamiltonian.

2. Ore’s Theorem

When in every pair of non-connected vertices u and v, the sum of their degrees, which is defined by the number of edges each vertex has, is at least equal to N, then the graph is Hamiltonian.

Example:

Under the graph (N = 5), the two nodes that do not have any connection when the degree of these nodes is 5 or more, are a positive indication of a Hamiltonian graph.

3. NP-Completeness

Determining whether a Hamiltonian path exists is an NP-complete problem. This implies that it is pretty simple to determine whether a solution is correct, but extremely difficult to find the solution for a large graph.

4. Every Complete Graph is Hamiltonian

When all the vertices are connected to each other, it is a complete graph, and every complete graph contains a Hamiltonian cycle.

5. Not All Graphs with Hamiltonian Paths are Hamiltonian Graphs

It is not always true that when a graph contains a Hamiltonian path (visits each vertex at least once), then the graph contains a cycle. To be a Hamiltonian graph, it should provide you with the ways to go back to the initial place as well.

A Graph and Its Hamiltonian Cycle

In the image below, you can see the Hamiltonian cycle traced by red lines. See how all vertices are visited once, and one edge from C to E is left, but it is still a Hamiltonian graph.

How to Determine if a Graph is Hamiltonian

In case you wish to know whether a graph is Hamiltonian, what you are essentially asking is whether this graph has a cycle that covers all the vertices in a single visit (i.e., visits each vertex only once) and returns to the original vertex. However, unfortunately, no universal rule exists. This is an NP-complete problem, i.e., it is difficult to solve quickly as the graph grows. We shall try using the methods we specified earlier to show you how to implement them:

1. Use Dirac’s Theorem

The theory says: If a graph has n ≥ 3 vertices, and every vertex has a degree ≥ n/2, then the graph is Hamiltonian.

Example: If your graph has 6 nodes, and each node connects to at least 3 others, you’re good to go.

2. Try Ore’s Theorem

Ore’s theorem says:

If the sum of degrees of any two non-connected vertices is ≥ n, then the graph is Hamiltonian.

Both theorems give sufficient conditions, but not necessary ones. So even if your graph doesn’t meet them, it might still be Hamiltonian.

3. Brute-Force Method

This method can be used for small graphs. Here you can try all possible permutations of different nodes to see if any form the required Hamiltonian cycle. The method is definitely slow, but it works very well in cases involving smaller graphs.

C++ example code:

Output:

Explanation: Here, the above C++ program will examine whether a given graph will have a Hamiltonian cycle in a brute-force fashion. It generates a list of the indices of all the vertices and forms all possible permutations (orderings) of them. In every permutation, it examines every next pair of vertices in the path and whether they are adjoined (via the adjacency matrix) and checks that the last point connects with the first one, therefore completing a cycle. When it discovers even a single such valid cycle, it says true, but when it runs out of possibilities, it says false. It is an easy and correct algorithm to use with small graphs, but on larger graphs it is soon impractical because it has factorial time complexity.

Example of a Hamiltonian Graph

For instance, suppose you have a graph of 5 points (or vertices), 0 through 4. The aim of the problem is to identify a path which passes every one of these points once (and only once), and back to the original point, a Hamiltonian cycle. Here is a C++ illustration of an adjacency matrix, an example of how each vertex is related to each other:

Backtracking Approach using C++:

Output:

Explanation: Here, each line in the matrix represents which vertices are connected. Here, 0→1→ 2 →4 →3 →0 is the path where each vertex is visited once a single time and then returns to the beginning. This forms a Hamiltonian cycle. The code you were provided is one of the most basic examples of how a Hamiltonian graph is used in actuality.

Differences Between Hamiltonian and Eulerian Graphs

Although Hamiltonian and Eulerian graphs might seem to be comparable graphs, they are used to solve quite different problems in graph theory. The knowledge of the distinction is the key to implementing the appropriate procedure when resolving a problem that involves a path/cycle.

Feature	Hamiltonian Graph	Eulerian Graph
Definition	Contains a cycle (or path) that visits every vertex exactly once	Contains a cycle (or path) that uses every edge exactly once
Visits	Each vertex once	Each edge once
Repetition	Edges can repeat, but vertices cannot	Vertices may be revisited, but each edge is used only once
Requirements	Must satisfy Hamiltonian cycle/path conditions (like Dirac’s or Ore’s theorem)	All vertices must have even degree (for Eulerian cycle)
Complexity	NP-complete (harder to solve)	Polynomial time (easier to check)

Consider a Hamiltonian graph as a delivery route, and you have to stop at every house once. An Eulerian graph, for example, is a street-cleaning path where no street (edge) can be cleaned twice, although you may go through the same house twice.

Real-World Applications of Hamiltonian Graphs

Hamiltonian graphs are not only an abstract concept that can be read in textbooks, but also a method that resolves real-life problems in many spheres. This is how you could face them in a real-life situation:

1. Traveling Salesman Problem (TSP)

Suppose you are a deliveryman who wants to visit each of the cities on his list and come home through the shortest path. That is precisely what the TSP does. A Hamiltonian cycle leads you to the shortest circuit whose elements are not revisited at all, which will prove ideal in route planning.

2. Genomic Sequencing

In molecular biology, sequencing fragments of DNA (called reads) requires reconstructing the original sequence, often using Hamiltonian paths. Every work (known as a read) is considered a node. They organize the reads in a form that reproduces the original sequence of DNA using a Hamiltonian path.

3. Best Path Planning

When it comes to city planning, robotics, and logistics, one should identify the routes that would allow covering all the required checkpoints with no loops. Hamiltonian graphs help determine whether such a route is even possible, and what the steps should be to achieve it.

4. Computer graphics and rendering

Hamiltonian cycles are useful in some graphics systems, especially mesh rendering or wireframe modeling, to figure out how to hit each edge or vertex, with a single drawing pass.

5. Circuit Design

Hamiltonian paths also assist in electronic circuit design by helping choose efficient component layouts with minimal wire usage and reduced overlap. (by trying to use the minimal path when minimizing the length of wire used, or in trying to avoid overlap among pairs of points, or in avoiding unnecessary jumps).

Conclusion

Learning about Hamiltonian graphs is relevant when you are new to graph theory or solving real-life practical applications, such as routing or genome sequencing, or designing a networking system. In a Hamiltonian graph, a Hamiltonian path (or Hamiltonian cycle) passes through every vertex of the graph once and only once, and the existence of such paths can be useful in solving problems more quickly. You have also learned some important theorems, such as that of Dirac and Ore, and the distinction between Hamiltonian graphs and Eulerian graphs, and even implemented a program to check for Hamiltonian cycles. On this basis, you may now look at more difficult applications or pass on to related graph problems.

Hamiltonian Graph- FAQs