The problem I am struggling to prove is the following:
Let $G$ be a connected simple graph with $n$ vertices and let $k<n$ be a positive integer. If $\deg(u)+\deg(v)\ge k$ for every pair of distinct vertices $u$ and $v$, then $G$ has a vertex disjoint path of length at least $k$, where, for a vertex $x$, deg$(x)$ stands for the degree of $x$.
The condition $\deg(u)+\deg(v)\ge k$, somehow, looks like the Ore condition in the discussion of Hamiltonian graphs.
Can someone show me the way to get into (or a counter example)?
