Dado un mapa si en cada vértice confluyen una cantidad par de estados, entonces se puede pintar el mapa con sólo dos colores de modo que no haya dos vecinos con el mismo color.

Se puede.
Empezamos con un estado E: lo pintamos de un color "A".
Luego pintamos los paises vecinos con otro color "B". Como en cada vértice confluyen una cantidad par de estados, dos vecinos de E no son vecinos entre si, es mas "entre" tales vecinos hay una cantidad impar de estados que sean fronterizos con E. Asi los podemos pintar de modo que no haya dos vecinos con el mismo color.
De esa manera vamos "avanzando" hasta pintar todo.

No es una demostracion pero tal vez a alguien le sirva.

PD. El mapa esta en el plano, no?

Lo que se trata es de pintar regiones, si mirás el grafo dual es pintar vertices. Si puedes dibujar un mapa con el grafo que indicas lo podes poner aquí y el problema va a estar resulto por al negativa .

Lo que pasa ahi es que los vértices tienen problemas. Hay dos vértices, por ejemplo, donde confluyen 1, 2 y el mar, o sea tres 'estados' (salvo que la gracia sea decir 'obviamente el mar es el mar, no un estado' )

¿Pero que pasa con este mapa que pongo a continuación?

Leo esta bien, pero... no es lo que tenia en mente. Para arreglarlo decimos que la cantidad de lineas fronterizas que confluyen en un vertice es par.

Bien, Un mapa más. Este no es 2 - coloreable, el mar es un estado, tiene 4 vértices, y en cada uno de ellos confluye un número par de estados. (Aunque el grado de los vértices en sí, sea impar)

Si el problema es: Si un grafo G, es plano y con todos sus vértices de grado par (lo que en principio no significa que concurran un nº par de estados), entonces su grafo dual, (o el mapa que determina) es 2-coloreable.

entonces la cosa cambia y no sirve ninguno de los dibujitos que estamos poniendo hasta ahora. De hecho, poner lazos no aportaría nada en este caso.