Graph Applications and the Traveling Salesperson In the class discussions, we have talked about how the traveling salesperson (TSP) problem and how it can be modeled using graphs. We also looked at...

HAMILTONIAN CYCLE:
The concept of Hamiltonian cycle had its inspiration from the great Mathematician of the North, Sir William Rowan Hamiltonian. Hamiltonian cycle is an integral part of the graph theory and can be defined as any cycle in a graph which passes through all the points in a graph exactly once. The concept of repetition is considered as invalid in the Hamiltonian system of Graphs. The process of finding any such line or cycle in a random graph is defined as the Hamiltonian cycle problem. There are many computer problems widely known which includes the Knights Tour problem or the Travelling Salesman Problem whose solution lies effectively in the process of finding a Hamiltonian cycle. The Hamiltonian cycle also has various applications in diverse fields like Algorithm design , Computer networks and also in exploration of biology in molecular levels .
There has been no such fixed method that can be applied for finding a Hamiltonian cycle for any given graph, hence the Hamiltonian cycle problem can be thought of a NP type ( non-Deterministic Polynomial ) based problem, the solution to which can be effectively found out using a non deterministic machine but usually deals with a great deal of complexity when tried using a deterministic machine or approach.
There are some basic techniques or theorems that enable us to distinguish between a Hamiltonian graph and a non Hamiltonian graph. The theorems are as follows:
Theorem 1:
For any given graph, if it is seen that each vertex of the graph possess a degree of two or greater than two, then it can be said that the two edges that are likely to be incident on that vertex will be a part of a Hamiltonian cycle.
Theorem 2:
For any graph, if there is an occurrence of any consecutive neighbours that possess a degree of two, then the possibility of existence of a Hamiltonian cycle is zero.
Theorem 3:
If there exists a vertex containing two neighbours a and b, each having a degree of two, then there cannot exists an Hamiltonian cycle which includes all the edges denoted by (v, x) where

Theorem 4:
The theorem states that if there exists a path of length in any random graph G where are the vertices then the Hamiltonian cycle will not include the starting the ending nodes. .
Theorem 5:
Each planar graph connected by 4 points must constitute a Hamiltonian Cycle.
Theorem 6:
Any graph possessing a vertex of degree of one cannot contain a Hamiltonian Cycle.
EULER CYCLE:
In the graph theory, any path which is constituted by a set of vertices, and they are so arranged in such a way that the adjacent edges intersect at same vertices. In other words any path that starts and ends in the same vertex is said as a cycle. An Euler cycle in any graph G can be defined as a set of points which when joined together touches each and every edge of the graph G.
In 18th century the great Mathematician Euler demonstrated a theory which removes the confusion of misconsidering each graph as an Euler cycle. The theorem states that:
The connected graph can be said to be an Euler cycle if and only if all the vertices has a degree of even nature.
This theorem basically demonstrated two independent statement. The first statement says...