Let G be a connected simple graph with $n \geq 3$ vertices. Suppose that there is a positive integer $k \leq n$ such that $d(u) + d(v) \geq k$ for every pair of non-adjacent vertices $u$ and $v$. Show that there is a path of length $k$ in $G$.
My first thought was that if $G$ is Hamiltonian it would contain a cycle of length $n$ which contains a path of length $k$, since $ k \leq n$.
Suppose $G$ is not Hamiltonian, so there is non cycle of length $n$ in $G$.
Let $P = v_0v_1 \dots v_{l}$ be an open path of maximum length $l$ in $G$. Suppose there is a cycle $C$ of length $r$ in $G$. Then $r <n$, so there is a vertex $w$ that does not lie on $C$. As $G$ is connected, there is a path form $w$ to $C$ which, together with $r-1$ edges of $C$, gives an open path of lengthe$\geq r$. Hence $r \leq l$.
See the end of the solution below.
Continuing the above line of thought:
Let $A=\{v_i \in V(P) : v_0v_{i+1} \in E(P)\}$ and $B=\{v_i \in V(P) : v_0v_{l} \in E(P)\}$. If $v_i \in A \cap B$ then $v_0 \dots v_iv_l \dots v_{i+1}v_0$ is a cycle of length $l+1$. Hence A and B are disjoint, so $|A|+|B|\leq |V(P)| = l+1$.
$v_0$ is not adjacent to $v_l$. All vertices adjacent to $v_0$ or $v_l$ are in $V(P)$, otherwise $P$ could be extended. Thus $|A| = d(v_0)$ and $|B| = d(v_l)$.
Hence $l +1 \geq d(v_0 +d(v_l) \geq k$, so $P$ contains a path of length k.