Let G be a graph so that for every v, deg(v) ≥ k. Show that G contains a path of length at least k and give an algorithm to find such a path.

Hint: Augment a path from both ends until there are no vertices outside the path, that are joined to the end vertices of the path.