Choose any vertex v in the first step. At each subsequent step, choose any random neighbor of the current vertex you are in that has not been visited before. You will get a valid choice for the next vertex for all the first k steps because each vertex has at least k neighbors and less than k vertices have been marked as visited.