Hamiltonian path

Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once.

A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.

• Ore’s Theorem (3.2) - A simple graph with $n$ vertices ($n\ge 3$) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is $n$ or greater.
• Dirac’s Theorem (3.3) - A simple graph with $n\ge 3$ vertices is Hamiltonian if every vertex has degree $\frac{n}{2}$ or greater.
• Question (3.6) - A simple graph with $n\ge 3$ vertices, and $n$ is odd, and every vertex has degree $\frac{n}{2}-1$ at least, then it contains Hamiltonian path.
• Question (3.7) - $K_{a,b}$ complete bipartite graph is contain Hamiltonian cycle, if and only if, $a=b$ and $a,b\ge 2$.