Hamiltonian cycles and paths. Necessary condition for the existence of a Hamiltonian cycle/path. Sufficient conditions: Dirac's and Ore's theorems.

Hamiltonian Cycle (!!!)

A Hamiltonian cycle in a graph G is a cycle that goes through every vertex of the graph exactly once. It is also called a spanning cycle. A graph that contains a Hamiltonian cycle is said to be Hamiltonian.

Hamiltonian Path (!!!)

A Hamiltonian path in a graph G is a path that goes through every vertex of the graph exactly once. Note: if a graph has a Hamiltonian cycle, then it also has a Hamiltonian path.

Necessary Condition for a Hamiltonian Cycle (!!!)

If a graph G is Hamiltonian, then for every S ⊂ V(G), the graph G \ S has at most |S| components.

Necessary Condition for a Hamiltonian Path (!!!)

If a graph G contains a Hamiltonian path, then for every S ⊂ V(G), the graph G \ S has at most |S| + 1 components.

Dirac's Theorem (!!!)

If G is a graph such that |V(G)| ≥ 3 and δ(G) ≥ n/2, then G is Hamiltonian. In other words, if every vertex has degree at least half the number of vertices, the graph is guaranteed to have a Hamiltonian cycle. ( δ(G) ≥ n/2 )

Ore's Theorem (!!!)

If G is a graph such that |V(G)| ≥ 3 and for any two non-adjacent vertices u and v, d(u) + d(v) ≥ n, then G is Hamiltonian. In other words, if every pair of non-adjacent vertices has combined degree at least n, the graph is guaranteed to have a Hamiltonian cycle. ( d(u) + d(v) ≥ n