Hamiltonian Graph

graph-theory

Definition

Hamiltonian Graph

A graph is called Hamiltonian graph if it possesses a hamiltonian line.

Theorems

Dirac’s Theorem

Dirac's Theorem

Every graph with $n$ vertices, in which each vertex has a degree of at least $\frac{n}{2}$, is Hamiltonian.

Ore’s Theorem

Ore's Theorem

Every graph with $n$ vertices, in which the sum of the degrees of any two non-adjacent vertices is at least $n$, is Hamiltonian.