graph theoryhamiltonian-path
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.
Suppose that $v$ is a vertex of degree $2$. If $G$ has a Hamilton circuit, that circuit must pass through $v$, so it must include both of the edges incident at $v$. In particular, if the configuration
o----o----o
u v w
occurs anywhere in $G$, it must be part of any Hamilton circuit in $G$. Such a circuit must be a circuit, so it must include some other path from $u$ to $w$ as well. This can be useful in proving that a graph does not have a Hamilton circuit: if there is no other path between $u$ and $w$ in $G$, then $G$ cannot have a Hamilton circuit.
Here's the lexicographically first Hamilton cycle (found using a backtracking algorithm):
Best Answer
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.