# can we use vertex degree to detect hamilton path and hamilton circuit?

Hamilton path: goes through every node/vertex exactly once.

Hamilton circuit: goes through every vertex exactly one and ends at the starting node/vertex.

So i am wondering is possible to use degree to detect if a graph have hamilton paths or circuits. Like we do with eulers circuit , if every vertex in the graph have a even degree then we know that eulers circuit exists.

Check the theorems of Ore and Dirac.

According to the theorem of Ore:

Let $G$ be a (finite and simple) graph with $n ≥ 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 ≥$ $n$ for every pair of non-adjacent vertices $v$ and $w$ of $G$

then $G$ is Hamiltonian.

According to the theorem of Dirac:

A simple graph with $n$ vertices $(n ≥ 3)$ is Hamiltonian if every vertex has degree $n / 2$ or greater.

• What do you mean by Hamiltonian? path or circuit – humble24 Oct 29 '15 at 19:00
• Dirac = circuit. Ore = path – kjanko Oct 29 '15 at 19:14
• alright, for Ore do i just pick a random pair of non-adjacent vertices ? do i have to check for every possible pair of vertices , or isit enough with one random pair of non-adjacent vertices ? – humble24 Oct 29 '15 at 19:36
• Every pair of non-adjacent vertices. – kjanko Oct 29 '15 at 19:39
• alright, thanks – humble24 Oct 29 '15 at 19:53