Prove that there exists a path in G of length K

Let $G=(V,E)$ be a nonempty graph and let $d(v)\geq k$ for all $v\in V$. Prove that there exists a path in $G$ of length $k$.

Alright so my first intuition is $$\sum_{i=1}^{n} d(v_i) \geq nk \quad(n=|E|)$$

So a path contains each vertex once and has no cycle. Seeing as each vertex has a degree $\geq k$, in the worst situation (because this limits the length of our path) we have: $$\sum_{i=1}^{n} d(v_i) = nk$$

We also have $\sum_{v\in V} d(v_i) = 2|E|$, so $$2|E| = nk.$$

This seems logical but I cant translate this into the length of a path. Any tips? edit maybe we can say because we have $\frac{nk}{2}$ edges, and $n$ vertices, we could maybe use induction?

Hint. Pick a vertex $v_1$. It is connected to $k$ vertices. Pick one of them $v_2$, this is connected to $k$ vertices, and $k-1$ of them are not in the path (only $v_1$ can be).
$v_2$ is connected to at least $k-2>0$ vertices not in the path. Pick one of them, $v_3$ repeat....
Induction by $k$ is probably the simplest way to write the solution....
• I wrote down take $v_1$ as your starting vertex, you can choose from $k$ edges to continue your path. The next vertex $v_2$ should have $k-1$ useable paths (no vertex can be visited twice) and so on until $v_k$ where it has $(k-k)$ useable verteces. But my problem is after $v_3$ because it can also have $k-1$ edges to pick from right? – WiseStrawberry May 30 '13 at 16:34
• $v_3$ is connected to $k$ vertices. One of them is $v_2$, another one MIGHT be $v_1$, but there are at least $k-2$ vertices which are not $v_1,v_2$ or $v_3$. Just pick one of them at random. – N. S. May 30 '13 at 16:36