If $deg(u)+deg(v) \ge n-1$ for $u$ and $v$ are non adjacent vertices, then G has Hamiltonian path
Solution 1:
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$?