2014

Maggio 2014 - problema 4

Si vuole colorare una cartina dell'Italia in modo che regioni adiacenti abbiano colori distinti.
Si dimostri che sono necessari almeno 4 colori.

Livello di difficoltà: Orsacchiotto tenerone
Punteggio difficoltà: 4



Il problema e' stato correttamente risolto da tutti coloro che hanno inviato una soluzione.
Possiamo associare ad ogni regione d'Italia un vertice di un grafo, e collegare due vertici di questo grafo con un arco quando gli estremi corrispondono a regioni adiacenti.
Il problema allora e' quello di provare che il numero cromatico \(\chi(G)\) del grafo di adiacenza \(G\) delle regioni italiane e' almeno pari a 4.
E' piuttosto immediato constatare che Umbria, Toscana, Marche e Lazio sono a due a due adiacenti, ragion per cui \(G\) contiene un sottografo completo su 4 vertici (\(K_4\)), e ognuno di questi vertici dev'essere necessariamente associato ad un diverso colore (\(\chi(K_4)=4\)): la tesi segue immediatamente. E' doveroso menzionare che per il noto Teorema dei quattro colori ogni grafo planare (ossia realizzabile nel piano senza che vi siano archi che si intersecano, se non nei vertici) ha numero cromatico minore o uguale a 4: poiche' il grafo di adiacenza delle regioni italiane e' ovviamente un grafo planare, tale teorema ci assicura che per colorare la cartina d'Italia rispettando i vincoli prescritti quattro colori siano non solo necessari (il che e' la tesi del problema) ma anche sufficienti, da cui \(\chi(G)=4\).