@gaizka
Resumiendo el post anterior: dado un grafo (es preferible razonar con grafos, son más manejables y se demostró que es equivalente al mismo problema con los mapas) 4-coloreable, deberías demostrar que TODOS los grafos que puedes construir añadiendo un nodo también lo son. (Esto obliga implícitamente a considerar todos los grafos 4-coloreables que tienes de partida. ¡Por eso usaron la computadora!).
Saludos!