Yesterday I asked a question about how to find hamiltonian paths and circuits in a graph, and I got the following answer:
According to the theorem of Ore (to find paths):
Let $G$ be a (finite and simple) graph with $n \geq 3$ vertices. We denote by $\deg v$ the degree of a vertex $v$ in $G$, i.e. the number of incident edges in $G$ to $v$. Then, Ore's theorem states that if
$\deg v + \deg w \geq n$ for every pair of non-adjacent vertices $v$ and $w$ of $G$
then $G$ is Hamiltonian.
According to the theorem of Dirac (to find circuits):
A simple graph with $n$ vertices $(n \geq 3)$ is Hamiltonian if every vertex has degree $n / 2$ or greater.
So after doing some exercises in the book, I got a bit confused. On one question they are using Ore's theorem to prove that there is a circuit. How?
Also in the book, they have given the following formulas:
$\deg x + \deg y \geq n$ then we have a hamilton circuit.
$\deg x + \deg y \geq n-1$ then we have a hamilton circuit.
So I am confused about which formula to use? When should I use Ore's theorem and when should I use Dirac's theorem?