Hamiltonian path is a path that contains all of the vertices of the graph. I know that if $deg(u)+deg(v) \ge n$ for every two non adjacent vertices $u$ and $v$ then the graph has Hamiltonian cycle and every Hamiltonian cycle is Hamiltonian path, too.
So I thought I just need to prove that if in a graph for every two non adjacent vertices $u$ and $v$, $deg(u)+deg(v) = n-1$ then the graph has Hamiltonian path. But I have no idea how to continue! Any help?
Best Answer
Hint: Let $G$ be a graph such that for all nonadjacent $u,v$, we have $d(u) + d(v) \geq n-1$. Create a new graph $G+w$ of order $n+1$ by adding a vertex $w$, and making $w$ adjacent to everything in $G$. Can you show that $G+w$ has a Hamiltonian cycle? And if so, can you use the Hamiltonian cycle in $G+w$ to find a Hamiltonian Path in $G$?