Prove that the bound is sharp. Theorem: Let $G$ be a graph of order $n\geq 3.$ If $$\deg u+\deg v\geq n$$ for each pair $u ,v$ of nonadjacent vertices of $G$ then $G$ is Hamiltonian.  
I have to show that this bound is sharp. I tried to consider $\deg u+\deg v= n-1$ to get some insights, but couldn't find anything useful. Frankly, I don't even know how to approach such problems so I would be grateful if someone could share his/her thoughts on how to approach problems of such kind and also give hints regarding this problem. 
 A: Note that all Hamiltonian graphs are connected, since given any two vertices we can walk along the Hamiltonian cycle to get from one to the other. So this tells us that if a graph is not connected, it can't possibly be Hamiltonian. In fact more is true; for any two distinct vertices $u,v$ in a Hamiltonian graph, there exists two paths $P,Q$ from $u$ to $v$ which only meet at $u$ and $v$. To see this just imagine the Hamiltoian cycle is a circle, $u,v$ are points on the circle. Then there are two paths from $u$ to $v$, going clockwise around the circle and going anticlockwise. These give the two required paths. 
This property of having two disjoint paths between any two vertices is much easier to work with than the Hamiltonian property.
Applying this to your problem, consider an $m$-regular graph $H$ on $m+1$ vertices (can you think of such a graph?). By definition every vertex in $H$ has degree $m$. Now let $H'$ be an identical copy of $H$ and take the graph $K$ to be the disjoint union of $H$ and $H'$. Given any two non-adjacent vertices $u,v$ in $G$, one can show that: $$\deg u+\deg v= 2m$$
We are not quite done, since we would like to change $2m$ to $2m+1$ to solve your problem. There are two cases.
Suppose $n$ is even and let $n=2m+2$. As mentioned, the graph $K$ does not quite meet the requirements on the degree. Let's pick a vertex $w$ in $H$ and add an edge between $w$ and every vertex of $H'$ to form a new graph $G$. We see that $G$ satisfies the degree requirement (why?) and because every path between a vertex in $H$ and a vertex in $H'$ must pass through $w$, we see that $G$ is not Hamiltonian (why?).
For $n=4$, this graph $G$ is a lone vertex connected by exactly one edge to a triangle (the point of the triangle it is connected to is $w$).
Now suppose $n$ is odd and let $n=2m+3$. The graph $K$ previously constructed only has $2m+2$ vertices, so let's add a new vertex $w$ and add an edge between $w$ and every other vertex in $K$. Call this new graph $G$. We see that $G$ satisfies the required condition on the degrees of non-adjacent vertices (why?). Now note that any path from a vertex in $H$ to a vertex in $H'$ must pass through $w$. So as in the previous case, $G$ can't be Hamiltonian (why?).
For $n=3$, this graph $G$ is a triangle with one of its edges removed (the vertex of degree $2$ is $w$).
A: HINT:-
Let the length of longest path in the graph be $k\le n$, and P be a longest path with endpoints $u$ and $v$. All neighbours of $u$ and $v$ must lie in P otherwise P can be extended. Since $\deg u+\deg v\geq n$, $u$ and $v$ must have at least two neighbours in common.
