# Hamiltonian Graphs

**Understanding Hamiltonian Graphs**

- A
**Hamiltonian graph**is a type of graph that possesses a**Hamiltonian cycle**, a closed loop that visits each vertex in the graph exactly once. - A
**Hamiltonian path**is similar to a Hamiltonian cycle but it does not need to return to the starting vertex. - It is named after the Irish mathematician Sir William Rowan Hamilton who studied paths and cycles in such graphs.

**Properties of Hamiltonian Graphs**

- There is no general formula to determine whether a graph is Hamiltonian or not, as this problem is known to be
**NP-complete**. - The concept of the Hamiltonian graph plays a significant role in various fields of studies such as in computer science, information routing, and network topology.
- A
**complete graph**with more than two vertices is always Hamiltonian as it possesses a Hamiltonian cycle. - If a graph has a vertex of
**degree one**, it cannot be Hamiltonian, since a cycle would require at least two edges incident to each vertex.

**Dirac’s and Ore’s Theorems on Hamiltonian Graph**

**Dirac’s theorem**states a sufficient condition for a graph to be Hamiltonian: if every vertex in the graph has a degree half the total number of vertices or more, the graph is Hamiltonian.**Ore’s theorem**is an extension of Dirac’s theorem: if the sum of the degrees of any two non-adjacent vertices is greater than or equal to the total number of vertices in the graph, then the graph is Hamiltonian.

**Hamiltonian Circuits and the Traveling Salesman Problem**

- The Hamiltonian cycle problem is famously related to the
**Traveling Salesman Problem**(TSP), an optimization problem trying to determine the shortest possible route for a salesman who needs to visit a set of cities and return to the starting point. - While it may seem simple to state, both the Hamiltonian cycle problem and the Traveling Salesman Problem have been proven to be
**NP-hard**, meaning no efficient solution exists that is guaranteed to be correct for all cases.