Problem on Graph Coloring A planar map is called non-degenerate if all vertices have degree $3$ that is borders of only $3$ countries meet at a point. Suppose that in a non-degenerate planar map, all faces have an even number of edges (or all countries have an even number of neighbours). Show that such a map can
be coloured in 3 colours.
 A: Up to a permutation of the colors there is exactly one such three-coloring.
Let ${\mathbb Z}_3$ be the set of colors. The following construction makes use of the cyclic additive structure of ${\mathbb Z}_3$.
Assume that we have such a three-coloring of the map. Consider a country $f$ and its $2k$ neighbours. When the country $f$ gets color $0$ its neighbours obtain alternatively colors $1$ and $-1$. This means that at the $2k$ vertices of $f$ we alternatively have the cyclic color orders $(0,1,-1)$ and $(0,-1,1)$. Mark these vertices with $1$, resp., $-1$ accordingly. The sum of all markings along the boundary of $f$ then is $0$. This works for each country $f$ of the map, of course with other colors for the individual participating countries. In all we obtain a $\pm1$ marking of the vertices of the map such that the ends of each edge are marked differently.
Conversely: Whenever all countries have  an even number of edges such a marking is possible, and it then determines a three-coloring of the map up to a permutation of the colors. That this works follows from Heawood's theorem (1898) in the theory of four coloring: Such a marking determines in any case a four-coloring, but the special properties of the present marking cause it to be a three-coloring. The topology of $S^2$ plays a rôle here. For more details see this paper.
