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$ )
- Find a vertex of degree <= 5 ($ k-1$ )
- Remove this vertex
- Color the rest of the graph using a recursive call
- 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?