6 color theorem on planar graphs recursive implementation

Question

I'm practicing my recursion skills at the moment and came across the 6 color theorem that states:

Every planar graph can be colored with 6 colors.

That theorem follows from the observation that every planar graph G has a vertex v that as a degree of less than or equal to 5.

The idea is pretty easy: choose v with degree less than or equal to 5. Color G-v inductively. Use the 6^th color for v.

I tried to implement that theorem recursively in pseudo code:

colorPlanarGraph(planar Graph G=(V, E)) 
    if |V| <= 6 then 
        color every node with a different color 0, ..., 5
    
    v = vertex with degree less than or equal to 5
    G' = colorPlanarGraph(G-v)
    colors = [true, true, true, true, true, true] 
    
    foreach u in Adj[v] do
        colors[u.color] = false; 
    for i=0 to 5 do 
        if colors[i] then 
             v.color = i
             break

Is this pseudo code correct and can I transform every inductive proof into a recursive algorithm?

Answer 1

Is this pseudo code correct

It looks fine to me. We'd have to see details to understand its complexity, but it certainly makes sense.

and can I transform every inductive proof into a recursive algorithm?

I'm not sure that this question makes sense. A proof doesn't necessarily translate into something that can be described with an algorithm. Possibly this would work for a proof of an existence theorem. (Here we prove the existence of a 6-coloring.) But I'm not even sure about that. And in other cases, I don't know what it would mean.