# Trying to understand Kempe’s algorithm for Graph Coloring

I am trying to understand Kempe’s algorithm to $$k$$-color a planar graph. This is what I understand till now:

Trying to 6-color a planer graph ($$k=6$$)

1. Find a vertex of degree <= 5 ($$k-1$$)
2. Remove this vertex
3. Color the rest of the graph using a recursive call
4. Put the vertex back, since its degree was at most 5 ($$k-1$$), we still have at least 1 color left to color this vertex

I understand this procedure but I was curious about the first step: finding a vertex of degree at most $$k-1$$. What would happen if there is no such vertex in the graph? For example, all vertices have a degree $$> k$$. In that case will the algorithm fail?