Ore's theorem about Hamiltonian graphs | graph theory

Episode 41.

Ore's theorem about Hamiltonian graphs | graph theory.

Definition. A Hamiltonian cycle in a graph is a cycle that passes through all vertices of the graph.
Definition. A graph is said to be Hamiltonian if it has a Hamiltonian cycle.
Ore's theorem. For any graph $G$ on $n$ vertices, where $n \geq 3$, if for any pair of non-adjacent vertices $u$ and $v$ we have $deg(u) + deg(v) \geq n$, then the graph $G$ is Hamiltonian.

Mathematics. Discrete Mathematics. Combinatorics. Graph theory.
#Mathematics #DiscreteMathematics #Combinatorics #GraphTheory

The same video on YouTube:
https://youtu.be/Fm4Wr-RjT2M

The same video on Telegram:
https://t.me/mathematical_bunker/65