2.1. Hamiltonian Circuit

Hello everyone welcome to this lecture and the plan for this lecture is as follows. So, in this lecture we will discuss about Hamiltonian circuit. And we will discuss about some sufficiency conditions for the existence of Hamiltonian circuit in a graph namely the Dirac’s theorem and Ore’s theorem.

In this introductory segment, we set the stage for understanding Hamiltonian circuits and paths. A Hamiltonian circuit is a route through a graph that starts and ends at the same vertex, visiting every other vertex exactly once. The lecture will delve into important theorems that help us identify whether a graph has a Hamiltonian circuit.

Think of planning a road trip where you want to visit multiple cities and return to your starting point without visiting any city more than once. This scenario mirrors what Hamiltonian circuits represent in graph theory.

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. So, specifically a Hamiltonian circuit is a simple circuit. So, what do we mean by 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.

Here we clarify the concepts of Hamiltonian circuits and Hamiltonian paths. A Hamiltonian circuit requires starting and ending at the same vertex while covering every vertex of the graph exactly once. Unlike Euler circuits, where edges must be covered, the focus here is solely on visiting each vertex without repetition.

Imagine a city where each intersection represents a vertex. Traveling through all intersections without repeating any, and ending where you started, resembles a Hamiltonian circuit. Alternatively, a Hamiltonian path would allow you to start at one intersection and end at another, having visited each intersection only once.

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.

We differentiate between Hamiltonian and Euler circuits. An Euler circuit necessitates visiting every edge of the graph at least once, whereas in Hamiltonian circuits, only vertices are to be covered without repetitions. Understanding this distinction is crucial as it leads to different ways of analyzing a graph's structure.

If you think of a delivery route, for an Euler circuit, every street (edge) must be used at least once, even if a delivery point (vertex) is visited multiple times. In contrast, a Hamiltonian route allows for every delivery point to be visited only once, ensuring efficiency and minimal redundancy.

So, now the next interesting question will be is there a necessary and sufficient condition through which we can check whether a given graph is Hamiltonian or not. Unfortunately like Eulerian graphs where we have a single condition which was both necessary as well as sufficient.

This chunk introduces the idea of conditions necessary to determine whether a graph is Hamiltonian. Unlike Eulerian graphs, which have a clear criterion involving the even degree of vertices, Hamiltonian graphs do not have a single sufficient condition. Instead, we explore separate conditions that are either necessary or sufficient, which reflects the complexity of identifying Hamiltonian properties.

If you think of identifying good candidates for a team based on various criteria, some might be essential while others are simply helpful but not mandatory. This reflects the mixture of necessary and sufficient conditions seen in Hamiltonian graphs.

So, the first sufficiency condition is what we call Dirac’s theorem. So, it says that if you have a connected graph where the degree of every vertex is at least 2, then it is guaranteed that your graph is Hamiltonian.

Dirac's theorem offers a sufficient condition for a graph to be Hamiltonian. Specifically, if every vertex in a connected graph has a degree of at least 2, this guarantees the existence of a Hamiltonian circuit. It emphasizes the relationship between vertex connections and the likelihood of finding Hamiltonian properties.

Think of a company where every employee needs to work with at least 2 other employees on a project. This interconnection increases the chance of concluding projects successfully, similar to how sufficient connections among graph vertices increase the likelihood of forming Hamiltonian circuits.

Whereas another related sufficiency condition is Ore’s condition which says that if your graph is such that for every pair of non-adjacent vertices u and v the summation of the degree of u and v is at least n then your graph is a Hamiltonian graph.

Ore's theorem serves as another nicety for ensuring a graph is Hamiltonian by considering pairs of non-adjacent vertices. According to Ore’s condition, if the sum of degrees of any two non-adjacent vertices is at least equal to the total number of vertices in the graph, it guarantees a Hamiltonian circuit's existence. This theorem enhances the flexibility in identifying Hamiltonian properties in complex graphs.

Imagine friends trying to plan a party; if two friends haven't met yet, but they are both connected to a significant number of other friends, the chance of planning a fun gathering increases. Similarly, in Ore's condition, the degree connection between vertices must be sufficiently strong to nurture a Hamiltonian circuit.

So, what we will prove here we will just discuss a very high level overview of the proof of Ore’s theorem. So, what we want to argue here is the following you are given a graph which has at least 3 vertices because then only it makes that to talk about the summation of degrees of non-adjacent pair of vertices.

In this section, we outline the proof of Ore’s theorem, which requires at least three vertices to formulate discussions regarding non-adjacent pairs. The proof will leverage logical reasoning to demonstrate that if Ore's condition holds, the graph must be Hamiltonian. This approach emphasizes logical deduction over technical algorithms.

Think of a debate among three friends about who to invite to a party. If any two have enough mutual friends among them, they can effectively encourage the third friend to join as well, thereby connecting all three, similar to how Ore's theorem connects vertices in a graph.

So, the way I construct my graph H from the graph G is the following I keep on successively joining non-adjacent pair of vertices in my graph G that means I take my graph G.

In this part, we introduce a methodology to explore non-Hamiltonian properties by constructing a super graph. This involves iteratively joining non-adjacent vertices until a critical pair is established, which indicates a point of no return in discovering Hamiltonian properties. This construction allows for establishing plausible conclusions about the original graph's Hamiltonian status.

Think of trying to enhance a network of roads in a town. You keep adding connections (roads) between intersections (vertices) until you find significant routes that cannot be improved further. This iterative addition is akin to creating this 'super graph' where possibilities are explored.

In this lecture we introduced a definition of Hamiltonian circuits and Hamiltonian path and unlike Euler graphs, Euler circuits, Euler path where we are we have a single condition which is both necessary and sufficient for the existence of Euler circuit and Euler path we do not have a single condition which is both necessary as well as sufficient for the Hamiltonian circuit and Hamiltonian path.

This concluding segment summarizes the key points discussed regarding Hamiltonian circuits, paths, and the theorems that relate them. It emphasizes the complexity of defining a single necessary condition for Hamiltonian graphs, contrasting with the simpler Eulerian graph criteria. This reflection poses Hamiltonian circuits as an intriguing subject of study in graph theory.

Just as in life, where we often face multiple paths and decisions instead of a straightforward approach, Hamiltonian graphs require consideration of various conditions, enriching their study and understanding against simplistic paradigms.

--