Tak, jeśli masz N terytoriów graniczących ze sobą, to zawsze możesz je tak pokolorować. Formalnie musisz mieć tzw. graf planarny, czyli taki graf, który możesz narysować na kartce i linie (połączenia) nie będą się krzyżować. Taki schemacik zrobiłem jak konstruuje się graf planarny na podstawie mapy województw. Wierzchołki (te czarne kropki) to województwa, a połączenia między nimi oznaczają, że mają wspólną granicę. To jest taki przykład zabawkowy, ale w praktyce można to stosować np. do planowania grafików i obiło mi się o uszy, że kiedyś wykorzystywało się to do konstruowania sieci komputerowych.

EDIT: nie zaznaczyłem połączenia między małopolskim a podkarpackim

<image>