Primi elementi della teoria dei grafi

Ogni grafo planare è 5-colorabile

La formula di Eulero permette di stabilire che:

In ogni grafo planare semplice il numero degli spigolo S, non può essere maggiore di 3V - 6 (dove V è il numero dei vertici).

Partendo da questa relazione si può dimostrare che:

Ogni grafo planare semplice ha almeno un vertice con grado minore o uguale a 5.

Infatti, se supponiamo che in un grafo semplice planare ogni vertice abbia almeno grado 6 allora deve valere l'uguaglianza 2S = 6V e cioè S = 3V. Ma ciò non è possibile perchè si avrebbero troppi spigoli rispetto al numero dei vertici e il grafo non potrebbe essere planare.

Nel 1890 Heawood riuscí a dimostrare che ogni grafo planare semplice è 5-colorabile mostrando che ogni insieme di 6 vertici può essere colorato con solo cinque colori. Vediamo il passo principale di questa dimostrazione. In un grafo planare semplice con n ≥ 6 vertici consideriamo un vertice X con grado cinque che avrà intorno a sè cinque vertici adiacenti che indichiamo con i numeri 1, 2, 3, 4, 5. Supponiamo che tutti i vertici adiacenti X abbiano colori diversi e quindi in questa situazione occorrono 6 colori distinti.

Consideriamo i vertici 1 e 3 (che sono colorati in blu e giallo) e supponiamo che non esiste nessun percorso P che collega il vertice 1 al vertice 3.

In questo caso possiamo scambiare il colore blu con il colore giallo e viceversa di tutti i vertici collegati con il vertice 1 e assegnare a X il colore blu.

In questo modo vengono utilizzati solo 5 colori. Ora, supponiamo invece che esiste un percorso P che collega il vertice 1 al vertice 3.

In questo caso essendo X collegato sia con il vertice 1 che con il vertice 3 il percorso P è chiuso e il vertice 2 è interno alla curva chiusa mentre il vertice 4 è esterno a tale curva. Non può esserci quindi nessun percorso che colleghi 2 con 4. Possiamo allora assegnare al vertice 4 lo stesso colore del vertice 2 e dare a X il colore del vertice 4 in questo modo vengono utilizzati solo 5 colori.