El problema del número de colores necesarios

Stephen Barr cuenta el caso del pintor que deseaba realizar sobre un gran lienzo la obra abstracta cuyo boceto se muestra arriba. Al fin se decidió a utilizar tal solo cuatro colores; cada región habría que quedar pintada de un solo color sólido, y de tal modo que hubiera colores distintos a cada lado de cada segmento común a dos regiones.

1. ¿Tiene solución el problema? En ese caso, ¿cuál es? y

2. ¿hay soluciones distintas?
3. Si no tiene solución explique por qué.

Ahora…Supongamos que deseamos colorear el mapa que sigue de modo que no haya dos regiones fronterizas del mismo color.

4. ¿Cuántos colores son necesarios?