The existence of a path of a length given I got stuck on this problem from my graph theory class. The problem goes

Let G a connected graph with n vertex,if there is a k positive integer such that
$$ 2\leq{k}\leq{n-1} \text{ and } (xy\notin{E(G)} \implies{} deg(x)+deg(y)\geq{k})$$
then there is a a path of length k in G.

Any hint?
 A: This is actually a fairly challenging exercise.
Are you familiar w the proof of Ore's Thm?

*

*If, for any integer $k'$; $3 \le k'<n$ $=|V(G)|$, there is a cycle with $k'$ vertices in $G$, then that $G$ is connected implies that there is a path w $k'+1$ vertices. This is true for general graphs $G$. See if you can see why.


*Let $k'$ be an integer less than $k$, such that a longest path $P$ in $G$ has $k'$ vertices. Write $P'=v_1v_2\ldots v_{k'}$, where $v_1$ and $v_{k'}$ are the endpoints of $P$. Then $v_1$ and $v_{k'}$ both have all neighbors in $P$ each, lest $P'$ could be extended. And furthermore, per 1., $v_1$ and $v_{k'}$ are not adjacent to each other. So furthermore, $d_G(v_1)+d_G(v_{k'})$ must be at least $k$.


*But then by the proof of Ore's Thm [see e.g., Wikipedia] 2. implies that there is a cycle on $v_1,\ldots, v_{k'}$ $= V(P)$ that contains all $k'$ vertices after all. So conclude using 1. that there is indeed a path w $k'+1$ vertices.
The condition that $G$ is connected is necessary; otherwise $G$ could be a collection of vertex-disjoint cliques with somewhere between $k/2+1$ and $k-1$ vertices each.
