Inseriamo un nodo in ogni regione e uniamo due vertici con uno spigolo se e solo se le regioni corrispondenti hanno un confine comune. Si ottiene cosí un grafo planare duale della mappa.

Nel passaggio tra la mappa e il corrispondente grafo duale le regioni si trasformano in vertici e i confini si trasformano in spigoli. Possiamo, ora, risolvere il quesito utilizzando solo quattro colori in modo che due vertici adiacenti abbiano colori diversi. Ecco una possibile colorazione:

Ed ecco il passaggio dal grafo alla mappa: