Let $k$ and $n$ be integers with $1 \leqslant k<n$. Show that every connected graph of order $n$, in which $d(u)+d(v) \geqslant k$ for every pair $u, v$ of non-adjacent vertices, contains a path of length $k$.

Let $k$ and $n$ be integers with $1 \leqslant k \leqslant n$. Show that a graph of order $n$ that contains no path of length $k$ has at most $(k-1) n / 2$ edges, and that this value is achieved only if $k$ divides $n$ and $G$ is the union of $n / k$ disjoint copies of $K_{k}$. [Hint: Proceed by induction on $n$ and consider a vertex of minimum degree.]