Prove that there is a path of lenght k+1 in a graph with minimum degree k I am faced with this question.


  Let $G$ be a graph in which each vertex has degree at least $k$. Show
  that there is a path of length $k$ in $G$ - that is, a sequence of $k+1$ distinct vertices $v_0, v_1, ..., v_k$ such that for $0 ≤ i &lt; k$, $v_i$ is connected to $v_{i+1}$ in $G$.


I started attacking it this way:

If $G$ has a vertex of degree atleast $k$, it has atleast $k+1$ vertices. That is, $G$ can have $|v| \geq k+1$

In the case where $|v| = k+1$, the graph is a fully connected graph of $k+1$ vertices, which trivially has a path of length $k+1$.

I am not able to prove the cases where $|v| \geq k+2$
Hint. Build up the path, using the minimum degree condition to show that you can extend it as much as you need to.