For all non-negative integers k, construct a tree T with maximum degree k and ordering

of V(T) so that the greedy-coloring with respect to this ordering uses k + 1 colors.

If someone could show this proof, It greatly appreciated!!! My professor gave a hint and said to do this by induction...