Tashkent university of information technologies named after muhammad al-khorazmi, ministry of information technology and communication development of the republic of uzbekistan

Example – Which graphs shown below have an Euler path or Euler circuit? 


Solution –  has two vertices of odd degree  and  and the rest of them have even degree. So this graph has an Euler path but not an Euler circuit. The path starts and ends at the vertices of odd degree. .
Hamiltonian paths and circuits :
Hamiltonian Path – A simple path in a graph  that passes through every vertex exactly once is called a Hamiltonian path
Hamiltonian Circuit – A simple circuit in a graph  that passes through every vertex exactly once is called a Hamiltonian circuit. 
Unlike Euler paths and circuits, there is no simple necessary and sufficient criteria to determine if there are any Hamiltonian paths or circuits in a graph. But there are certain criteria which rule out the existence of a Hamiltonian circuit in a graph, such as- if there is a vertex of degree one in a graph then it is impossible for it to have a Hamiltonian circuit. There are certain theorems which give sufficient but not necessary conditions for the existence of Hamiltonian graphs. 
Dirac’s Theorem- “If is a simple graph with  vertices with such that the degree of every vertex in is at least , then has a Hamiltonian circuit.” 
Ore’s Theorem- “If is a simple graph with  verticeswith such that for every pair of non-adjacent vertices  and  in  , then  has a Hamiltonian circuit.” 
As mentioned above that the above theorems are sufficient but not necessary conditions for the existence of a Hamiltonian circuit in a graph, there are certain graphs which have a Hamiltonian circuit but do not follow the conditions in the above-mentioned theorem. For example, the cycle has a Hamiltonian circuit but does not follow the theorems. 
Note: K_n is Hamiltonian circuit for 
There are many practical problems which can be solved by finding the optimal Hamiltonian circuit. One such problem is the Travelling Salesman Problem which asks for the shortest route through a set of cities. 

• 
  Example 1- Does the following graph have a Hamiltonian Circuit? 
  

Given an undirected Graph consisting of N nodes in the form of an adjacency matrix graph[][] of size N*N, the task is to print all Hamiltonian cycles possible in the given undirected Graph (taking starting vertex as ‘0’).
A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in the graph) from the last vertex to the first vertex of the Hamiltonian Path.