$G$ connected, $d(u)+d(v)\geq k$ for $u,v$ non-adjacent, then $\exists$ path of length $k$ Theorem. Let $k$ and $n$ be integers with $1\leq k<n$. Every connected graph of order $n$, in which $d(u)+d(v)\geq k$ for every pair $u,v$ of non-adjacent vertices, contains a path of length $k$.
Idea for proof. I tried something similar to a proof of $\delta(G)\geq n/2 \implies G$ Hamiltonian. Consider a longest path $P=x_1,\ldots,x_j$ in $G$. Suppose $j<k$. All neighbours of $x_1$ and $x_j$ lie in $P$, and $d(x_1)=d(x_j)\geq k$, so we can find $x_i, x_{i+1}$ adjacent to $x_j, x_1$, respectively.
Problem. This gives a cycle length $j+1$ but only a path of length $j$, for we measure the length of a path in edges.
Can I tweak my approach or do I need to prove it in a completely different way?

The proof works. There is just a silly last step I missed.
$G$ is connected and of order $n>k\geq j+1$. So given a cycle of length $j+1$ there must be a vertex not on the cycle but adjacent to it. This gives a path of length $j+1$.
