2.1.1. Definition of Hamiltonian Circuit and Hamiltonian Path

So, what is a Hamilton Circuits and Hamilton Paths? So, on a very high level it is a version of travelling salesman problem in incomplete graphs.

In this chunk, we introduce the concepts of Hamiltonian circuits and Hamiltonian paths, which are specific types of routes in graph theory. A Hamiltonian circuit is a loop that visits every vertex exactly once and returns to the starting point. Conversely, a Hamiltonian path visits every vertex exactly once but does not necessarily return to the starting point. Both concepts are related to the Travelling Salesman Problem, which seeks the shortest possible route visiting a set of locations.

Think of Hamiltonian circuits like planning a road trip where you want to visit several cities and return home without revisiting any city. A Hamiltonian path would be if you want to visit several cities but don't necessarily need to return home at the end of your trip.

A Hamiltonian circuit is a simple circuit. It is a tour which starts and ends at the same vertex and all the edges are distinct. But it is a special type of simple circuit in the sense that the vertices are not allowed to be repeated.

A Hamiltonian circuit is defined as a cycle within a graph that starts at a vertex, visits every other vertex exactly once, and returns to the starting vertex. In other words, it's a closed loop that covers all vertices of the graph without revisiting any vertex. This is different from other types of circuits, like Eulerian circuits, which focus on visiting every edge rather than vertices. The emphasis here is on distinct vertices.

Consider a game like Monopoly. If you start at 'Start', visit all the properties exactly once, and return to 'Start', you've completed a Hamiltonian circuit. You cannot land on the same property more than once during this round.

Hamiltonian path is a simple path that means it may not start and end at the same vertex. And it should cover exactly once each vertex of the graph.

A Hamiltonian path allows for a route through the graph where you can start at one vertex and end at another, without revisiting any vertex. Unlike the Hamiltonian circuit, the path does not need to close back on itself. It's crucial that each vertex in the graph is covered exactly once to qualify as a Hamiltonian path.

Imagine a mail carrier delivering mail in a large neighborhood. They can start at their main office (a vertex), deliver to every house (other vertices) without going back to any house, and finish at a different location. This delivery route illustrates a Hamiltonian path.

We call a graph as a Hamiltonian graph if it has at least one Hamiltonian cycle.

A Hamiltonian graph is defined by the existence of at least one Hamiltonian cycle. This means that within this graph, there is at least one way to traverse that visits each vertex exactly once and returns to the starting point. The property of being Hamiltonian is significant in graph theory because it helps identify specific structures and complexities within a graph.

Think of a competitive bike race that starts and ends at the same town while passing through every single checkpoint exactly once. If such a route exists, the race route can be seen as a Hamiltonian cycle, and the network of towns and checkpoints forms a Hamiltonian graph.

This is different from your Euler circuit. The Euler circuit, the requirement first at all the edges should be covered as part of your tour. Here the requirement is that all the vertices should be covered. And no vertex should be repeated.

The fundamental difference between Hamiltonian and Eulerian concepts lies in what is being covered in the respective paths or circuits. For Hamiltonian paths and circuits, the focus is on visiting all vertices exactly once. In contrast, for Eulerian paths and circuits, the goal is to traverse every edge of the graph at least once. Understanding this difference is crucial for correctly identifying and solving problems related to paths and circuits in graph theory.

Consider a mailman again: if they are required to visit every house in a neighborhood (Hamiltonian path) but can choose any path that doesn't repeat houses, that’s different from a situation where they must ensure every street is covered, even if it means visiting some houses multiple times (Eulerian path).

For instance if I consider the first graph here this, this graph has a Hamiltonian circuit because if I make a tour like a to d, d to e, e to c, c to b and b to a then it covers all the vertices. Whereas this graph, so this is the first graph it has an Hamiltonian circuit whereas the second graph it does not have a Hamiltonian circuit.

This chunk introduces examples to illustrate the differences between Hamiltonian circuits and paths. The explanation outlines a specific graph that contains a Hamiltonian circuit, detailing how it meets the requirements. The comparison with another graph that fails to have a Hamiltonian circuit highlights the concept more effectively, reinforcing the criteria for defining Hamiltonian graphs.

Imagine two theme parks: the first park is designed in a way that allows a guest to visit every attraction exactly once before returning to the entrance (Hamiltonian). The second park has poor design, leading them to miss attractions if they only stick to a specific path, which might not let them return to the entrance without backtracking (Non-Hamiltonian).

Unfortunately like Eulerian graphs where we have a single condition which was both necessary as well as sufficient. So, just to recall we had the condition that all the vertices of your graph should have even degree and that was both necessary as well as sufficient for the existence of an Eulerian circuits.

In contrast to Eulerian graphs, which have a straightforward condition for existence, Hamiltonian graphs lack a singular necessary and sufficient condition. While there are several sufficient conditions to assert if a graph is Hamiltonian, they are not necessary, meaning that a graph could still contain a Hamiltonian cycle without satisfying those conditions.

Think of baking: for a cake (Eulerian graph), you have a specific list of ingredients and amounts to ensure it rises correctly. For making a smoothie (Hamiltonian graph), you can use various fruits and liquids, but there’s no one recipe that guarantees a perfect blend — as long as you use at least some of each category, you might end up with a good drink.

So, what we will discuss; we will discuss in this lecture 2 important sufficient conditions for the existence of Hamiltonian graph. I stress that those 2 conditions are not necessary conditions.

In this segment, we are introduced to two significant sufficient conditions for determining if a graph is Hamiltonian: Dirac's theorem and Ore's theorem. These theorems provide criteria under certain conditions that guarantee the existence of Hamiltonian circuits, although they do not represent all possible Hamiltonian graphs.

You might think of them as guidelines for travelers. Just because you find a route that's busy and full of attractions (Dirac's theorem) or diverse locations (Ore's theorem) does not mean there are no unseen gems that could also lead you on an adventurous path.

--