Hamiltonian Graph

Think of a road trip across a country. A Hamiltonian graph is like planning a route that lets you visit all the major cities (visit every vertex or dot on the map) in one exciting journey:

1. Visit Every Place: You want to drive through every single city (visit every vertex or dot on the map) exactly once.
2. One Big Loop: This isn’t just any random trip. You want to end up back at your starting point (the cycle goes back to the first vertex).
3. No Shortcuts: You can only travel on the existing roads (use the edges that connect the areas).

Basically, a Hamiltonian graph is a map where you can create a perfect loop that hits every single spot on the map exactly once, without taking any shortcuts or backtracking.

Hamiltonian Cycle/Circuit and Path

Hamiltonian Cycle or Circuit in a graph G is a cycle that visits every vertex of G exactly once and returns to the starting vertex.

• If graph contains a Hamiltonian cycle, it is called Hamiltonian graph otherwise it is non-Hamiltonian.
• Hamiltonian Path in a graph G is a path that visits every vertex of G exactly once and Hamiltonian Path doesn’t have to return to the starting vertex. It’s an open path.

Hamiltonian Path in a grpah G is an open path that visits every vertex in the graph exactly once, but doesn’t necessarily return to the starting point.

A semi-Hamiltonian path is a path that visits every vertex once and starts and ends at different vertices. Semi-Hamiltonian graphs are sometimes called traceable.

If a graph has a Hamiltonian cycle then it automatically has a semi-Hamiltonian path (by just dropping off the last vertex in the cycle we create a path

Check if a graph is Hamiltonian

1. Brute Force Enumeration: The most straightforward approach is to systematically enumerate all possible permutations of vertices and check if any permutation forms a Hamiltonian cycle. However, this method is computationally expensive, especially for large graphs, due to its exponential time complexity.
2. Dirac’s Theorem: Dirac’s Theorem provides a sufficient condition for a graph to be Hamiltonian. According to Dirac’s Theorem, if a graph G has n vertices (where n > 2) and each vertex has degree (number of edges incident to it) at least n/2, then G is Hamiltonian. While this condition is not necessary, it can quickly verify Hamiltonicity for some graphs.
3. Ore’s Theorem: Ore’s Theorem offers another sufficient condition for Hamiltonicity. It states that if a graph G has n vertices (where n > 2) and for every pair of non-adjacent vertices, the sum of their degrees is at least n, then G is Hamiltonian. Similar to Dirac’s Theorem, Ore’s Theorem provides a quick check for some graphs.