A simple graph $G$ with $n$ vertices in which the sum of degrees of every two non-adjacent vertices is at least $n-1$ has a Hamiltonian path.
As described here, one can add a new vertex $w$ and connect it to other $n$ vertices, so that for each two non-adjacent $u,v\in V(G)$,$$\deg(v)+1+\deg(u)+1\ge n-1+2\\=n+1,$$ which, according to Ore's theorem, means $G+w$ is Hamiltonian, that is, there is a Hamiltonian cycle- a cycle passing through all the vertices of $G+w$. Now, if we remove $w$ and all the added edges connecting it to the initial $n$ vertices, we break a Hamiltonian cycle in $G+w$ and get a Hamiltonian path in $G$.
But, if we change the hypothesis to sum of degrees of every two non-adjacent vertices being at least $n-\color{red}2,$ the statement doesn't hold.
E. g., $n=6$ and $G$ consisting of $2$ triangles:
$d(u)+d(v)=4$ for each non-adjacent $u$ and $v$ and there is no Hamiltonian path.
Question:
Is there any example with $|V(G)|>6$ where $d(u)+d(v)=n-2$ for at least one pair of non-adjacent vertices $u,v\in V(G)$ and for other non-adjacent pairs $u,w\in V(G), d(u)+d(w)\ge n-1$ and $G$ doesn't have a Hamiltonian path?
Best Answer
No, there is no such example.
It is easier to ask: is there an $n$-vertex graph $G$ such that $\deg(u)+\deg(v) = n-1$ for one non-adjacent pair $u,v$, and $\deg(u)+\deg(v) \ge n$ for all other non-adjacent pairs, which does not have a Hamiltonian cycle? If the graph in your question exists, then by the adding-$w$ trick, this one must as well.
Suppose such a $G$ exists. Then $G+uv$ satisfies the hypotheses of Ore's theorem and has a Hamiltonian cycle. Either that cycle exists in $G$, or else $G$ at least has a $u-v$ Hamiltonian path: a path $(x_1, x_2, \dots, x_n)$ with $x_1 = u$ and $x_n = v$.
Suppose that $\deg(u) \ge 2$ (if not, look at $v$ instead of $u$), and let $x_i$ with $i>2$ be any neighbor of $u = x_1$. Then there is also a Hamiltonian path $(x_{i-1}, x_{i-2}, \dots, x_1, x_i, x_{i+1}, \dots, x_n)$ - and in this Hamiltonian path, $\deg(x_{i-1}) + \deg(x_n) \ge n$.
Now we can follow the standard proof of Ore's theorem to show that this Hamiltonian path can be turned into a Hamiltonian cycle. We conclude that $G$ is Hamiltonian; a single pair with $\deg(u)+\deg(v)=n-1$ is not enough to break the theorem.
In fact, a stronger argument can be made. Suppose that $G$ has fewer than $n-2$ non-adjacent pairs $u,v$ with $\deg(u)+\deg(v)=n-1$; for all other non-adjacent pairs $u,v$ the degree sum is $\deg(u)+\deg(v) \ge n$.
Then $G$ has a Hamiltonian path $(x_1, x_2, \dots, x_n)$ and by the argument above, we can turn this path into a total of $\deg(x_1) \cdot \deg(x_n)$ different Hamiltonian paths. Since $x_1, x_n$ cannot be adjacent, $\deg(x_1) + \deg(x_n) \ge n-1$, so $\deg(x_1) \cdot \deg(x_n) \ge n-2$. Therefore at least one of the Hamiltonian paths we get must end at vertices whose degree sum is at least $n$, and then the argument of Ore's theorem turns it into a Hamiltonian cycle.
The bound $n-2$ is tight: otherwise, take a $K_{n-1}$, and add a leaf vertex adjacent to one of its vertices. Here, there is no Hamiltonian cycle, and only $n-2$ pairs of non-adjacent vertices, each with degree sum $n-1$.
Similarly, for the Hamiltonian path question, we can take a $K_{n-1}$ together with an isolated vertex. Here, there is no Hamiltonian path, and only $n-1$ pairs of non-adjacent vertices, each with degree sum $n-2$. This is best possible.