# Check if Hamiltonian Cycle exists in a graph using Python

In this blog, we will find whether a graph contains a Hamiltonian cycle or not in Python

### What does one mean by a Hamiltonian path/cycle?

A hamiltonian path refers to a path that passes all the vertices of a graph exactly once.

Ex: A hamiltonian cycle refers to a cycle that passes all the vertices of a graph exactly once.

Ex: ### Algorithm:

To find the hamiltonian cycle we will be using backtracking along with DFS to traverse all the different types of hamiltonian paths possible.

• We first create a path list which will store the current path that we have traveled
• Then, we start a DFS from the root and keep appending the different root that we get as we traverse through the graph.
• Parameters we use to see if a node is safe to jump in DFS are:
• If a node does not exist in our already traveled path.
• If we have found a hamiltonian cycle, then we don’t need to traverse any further.
```#------------------------------------------
'''
Defining our safe vertex as
something which is not in our
path
'''
def safeVertex(node):
if(node in path):
return False

return True

#-------------------------------------------

#-------------------------------------------
'''
Defining our DFS and
Backtracking Logic
'''

def cycleDetection(E,n,root):
path.append(root)
#Seeing all the neigbours of the current root
for i in E[root]:
#Checking if our vertex satisfies the safe Vertex
if(safeVertex(i)):
#Checking if a cycle has already been detected or not in the
#---------------------previous recursion--------------------
if(cycleDetection(E,n,i)):
return True

#Checking if our current path has all the vertices
if(len(path) == n):
#If there is an edge from last vertex to the first vertex in our path
#-------------then we have an hamiltonian cycle---------------------
if(path in E[path[len(path)-1]]):
return True
else:
return False
#once we are done we remove that particle from the iteration
path.pop()

#-------------------------------------------

#-------------------------------------------
'''
Printing True or False
based on our output from Cycle Detection
'''

def HamiltonianCycle(E,n,root):
if(cycleDetection(E,n,root)):
print("True")
else:
print("False")

#-------------------------------------------

path = []

N_Vertices = int(input())

matrix = list()
for i in range(N_Vertices):
matrix.append([])

N_Edges = int(input())

for j in range(N_Edges):
edge_vertices = input().split()
u = int(edge_vertices)
v = int(edge_vertices)
matrix[u-1].append(v-1)
matrix[v-1].append(u-1)

HamiltonianCycle(matrix,N_Vertices,0)

#This path is actually a Hamiltonian cycle.
print(path)
```
```Input:
(this is essentially the graph which was given in the hamiltonian cycle example with 7 vertices)

7
10
1 2
1 3
1 6
6 7
7 5
2 3
3 4
3 5
4 5
5 6```
```Output:
True
[0, 1, 2, 3, 4, 6, 5]```