Grafi e retiIl Teorema dei Quattro Colori

Tutte queste mappe possono essere colorate con solo quattro colori diversi, ma come puoi immaginare altre mappe molto complicate hanno bisogno di molti più colori. In effetti, alcune mappe richiedono almeno quattro colori, ogniqualvolta contengano quattro paesi tutti collegati tra loro.

Come in precedenza, possiamo convertire una mappa con Paesi e confini in un grafo planare: ogni Paese diventa un verticeuno spigolouna faccia e i Paesi che condividono un confinehanno lo stesso colore sono connessi da uno spigolo:

Ora vogliamo colorare i vertici di un grafico e fare in modo che due vertici collegati da uno spigolo siano di un colore diverso.