Dirac's & Ore's Theorem: Checking Hamiltonian Graph Conditions

Determining Hamiltonian Graphs: Applying Dirac's and Ore's Theorems

This guide explores Dirac's and Ore's theorems, providing a step-by-step approach to check if a given graph fulfills their conditions to be classified as Hamiltonian.

What are Dirac's and Ore's Theorems?

• Dirac's Theorem: A simple graph with 'n' vertices (n ≥ 3) is Hamiltonian if every vertex has a degree of at least n/2.* Ore's Theorem: For a simple graph with 'n' vertices (n ≥ 3), if the sum of the degrees of any two non-adjacent vertices is greater than or equal to 'n', then the graph is Hamiltonian.

Checking the Conditions:

To determine if a graph satisfies these theorems, follow these steps:

1. Vertex Degree Check (Dirac's Theorem): * Calculate the degree of each vertex in the graph. * Compare each vertex's degree to n/2 (where 'n' is the total number of vertices). * If any vertex has a degree less than n/2, Dirac's theorem is not satisfied.

2. Non-Adjacent Vertices Check (Ore's Theorem): * Identify all pairs of non-adjacent vertices in the graph. * For each pair, sum their degrees. * If the sum is less than 'n' for any pair, Ore's theorem is not satisfied.

Conclusion:

By meticulously examining the degrees of vertices and the sums of degrees for non-adjacent vertices, we can ascertain whether a given graph meets the criteria outlined in Dirac's and Ore's theorems, and consequently, determine if the graph is Hamiltonian.