2.1.4. Proof of Ore's Theorem

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. So, it is given that you take any pair of vertices u and v which are non adjacent the sum of their degrees is at least n. Then I want to argue that my graph is indeed Hamiltonian.

Ore's Theorem states a condition under which a graph will contain a Hamiltonian circuit. To prove Ore's theorem, we start by considering a graph that has at least 3 vertices. The graph must meet the condition that for any pair of vertices (u and v) that are not directly connected by an edge, the sum of their degrees must be at least equal to the total number of vertices, n. If this condition is met, we will show that the graph includes a Hamiltonian circuit, meaning it is possible to traverse every vertex exactly once before returning to the starting vertex.

Imagine a group of friends at a party where each friend can be thought of as a vertex in a graph. If two friends do not know each other (non-adjacent), the number of mutual friends they have (degree of the vertices) must be high enough (combined degree at least n) for everyone to form a larger group and guarantee a fun conversation (Hamiltonian circuit).

And the proof will be by contrapositive that means we would not give you a concrete algorithm, by running which you can find out your Hamiltonian circuit or Hamiltonian tour but rather we will argue logically that indeed this implication is true. That means we are trying to give a non constructive proof where we are arguing proof by contrapositive.

The proof of Ore's Theorem employs a contrapositive approach, where instead of directly demonstrating that the graph is Hamiltonian under the given conditions, we will show that the absence of a Hamiltonian circuit leads to a failure of Ore's condition. In logical terms, we assert that if the graph is not Hamiltonian, then there exists at least one pair of non-adjacent vertices for which the sum of their degrees is less than n. This method does not provide a direct algorithm but rather relies on logical reasoning to confirm the theorem.

Think of this approach like a detective solving a mystery. Instead of showing who the suspect is, the detective proves that if the suspect is innocent (the graph is non-Hamiltonian), then there is at least one critical piece of evidence missing (the degree sum condition fails).

So, we will first transform the graph G to another graph H. And intuitively what is this graph H: it is the maximal non Hamiltonian super graph of G. Namely this graph H will have my original graph G and it might have some additional edges as well we will see how those additional edges are added.

In the proof, we create a new graph H that is derived from the original graph G. This graph H is a 'maximal non-Hamiltonian supergraph', meaning it includes all the vertices from G and additional edges may be added. The goal is to continue adding edges between non-adjacent vertices of G while ensuring the resulting graph H remains non-Hamiltonian. This construction will help us establish properties that contribute to validating Ore's condition.

Consider this as a team-building exercise where you aim to strengthen connections between friends (vertices) by adding new friendships (edges). You keep adding friendships, ensuring that the team remains unconnected (non-Hamiltonian), until you reach a point where a critical friendship will guarantee everyone knows each other in the group.

If you reach that point that means that is the saturation state and you should stop that means you should not now add the edge u and v. That means you have now identified a critical pair of non adjacent vertices u and v such that by adding the edge between u and v in the super graph you are bound to get a Hamiltonian cycle.

At a certain stage in constructing graph H, we identify a specific pair of non-adjacent vertices, u and v, such that adding an edge between them will create a Hamiltonian cycle. This indicates that the supergraph is on the verge of becoming Hamiltonian. This critical pair is essential because it shows the limits of the construction process for building a non-Hamiltonian graph.

Picture this as discovering a pivotal connection within a network. When two companies decide to partner (create an edge), they fill the last gap needed to unite all companies under one large cooperative network (complete circuit).

So, since I have now identified my node u and v which are the critical vertices what I can now say is the following. I can say that in my super graph H, I do have a Hamiltonian path. That Hamiltonian path will start with the node u and it will end with the vertex v and it will cover all the vertices of the graph.

Given our critical vertices u and v in the supergraph H, we can form a Hamiltonian path starting from u to v, covering all vertices. Since we established that adding the edge between them would form a Hamiltonian cycle, this path demonstrates that H is not just any path but a significant one that supports the broader conclusion about the original graph's characteristics.

Think of this Hamiltonian path as creating a tour route that starts and ends at key landmarks (u and v) in a city. While the tour passes through all important sites (vertices), the absence of a direct route between the two key landmarks ensures the uniqueness of this specific journey.

So that brings me to the end of this lecture. So, these are the references used and just to summarize: In this lecture we introduced a definition of Hamiltonian circuits and Hamiltonian path..

The lecture concludes with a summary of Ore's Theorem, highlighting that unlike Euler's conditions, there isn't a single sufficient and necessary condition for Hamiltonian circuits. The two main conditions discussed – Dirac's and Ore's condition – are sufficient for a graph to be Hamiltonian but not necessary, meaning there are graphs that satisfy Ore's condition and are Hamiltonian without fulfilling other mentioned conditions.

It's like discussing the various signs that indicate a healthy restaurant. While many healthy restaurants might have organic ingredients (Ore's condition), it doesn’t mean that every restaurant with organic produce is healthy if they also don't follow other essential health guidelines or maintain cleanliness.

--