What is a Hamiltonian cycle in a graph?

Hamiltonian cycles stand as one of graph theory’s intriguing and essential concepts. These cycles provide insight into graphs’ connectivity and traversal patterns, with applications ranging from network design to optimization problems. This Answer explores the properties of Hamiltonian cycles, their significance, and algorithms for their identification.

Hamiltonian cycles were named after Sir William Rowan Hamilton, an Irish mathematician who contributed significantly to mathematics and physics.

Properties of Hamiltonian Cycles

A Hamiltonian cycle in a graph visits every vertex exactly once, except for the starting and ending vertices, which are the same. Here are some important properties of a Hamiltonian cycle:

Necessary condition: Every graph with a Hamiltonian cycle must be connected.
Sufficient condition: If a graph $G$ has $n$ vertices (where $n > 2$ ) and for every pair of non-adjacent vertices $u$ and $v$ , the $\text{degree of }u ~+~\text{degree of }v$ is greater than or equal to $n$ , then $G$ has a Hamiltonian cycle. This condition is known as Dirac’s theorem.

Examples of Hamiltonian cycles

Let’s look at the following illustration to visualize Hamiltonian cycles:

from itertools import permutations
def has_hamiltonian_cycle_brute_force(graph):
    # Generate all permutations of vertices
    for perm in permutations(graph.keys()):
        # Check if the permutation forms a Hamiltonian cycle
        if len(perm) > 1 and all(graph[perm[i-1]][perm[i]] for i in range(1, len(perm))) and graph[perm[-1]][perm[0]]:
            return True
    
    return False
# Example graph with adjacency list representation
graph = {
    'A': {'B': True, 'C': True, 'D': True},
    'B': {'A': True, 'C': True, 'D': True},
    'C': {'A': True, 'B': True, 'D': True},
    'D': {'A': True, 'B': True, 'C': True}
}
print("Hamiltonian cycle: ", has_hamiltonian_cycle_brute_force(graph))

Backtracking algorithm

The backtracking algorithm utilizes a more systematic approach. It employs a depth-first search (DFS) algorithm to explore the graph, backtracking when necessary to explore alternative paths. By pruning the search space, backtracking efficiently navigates through the graph, identifying Hamiltonian cycles without considering every permutation. This approach is particularly effective for larger graphs, offering a more scalable solution than brute force methods.

Let’s look at the following code example to better understand the brute force approach:

def has_hamiltonian_cycle_backtracking(graph, path=[]):
    if len(path) == len(graph):
        # Check if the last vertex is connected to the starting vertex
        return path[0] in graph[path[-1]]
    
    for vertex in graph[path[-1]]:
        if vertex not in path:
            # Recursively explore all possible paths
            if has_hamiltonian_cycle_backtracking(graph, path + [vertex]):
                return True
    
    return False
# Example graph with adjacency list representation
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['A', 'B', 'C']
}
print("Hamiltonian cycle: ", has_hamiltonian_cycle_backtracking(graph, ['A']))

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

What is a Hamiltonian cycle in a graph?

Properties of Hamiltonian Cycles

Algorithms for identifying Hamiltonian cycles

Brute force algorithm

Backtracking algorithm

Conclusion