Ogni faccia di un grafo planare come quelli di cui ci stiamo occupando (cioè quelli che modellizzano una carta geografica, in cui ogni vertice è collegato al più a uno spigolo) è circondata da almeno 3 spigoli. Insomma, non ci occupiamo di grafi di questo tipo:
Siccome le facce sono almeno triangolari, cioè circondate da almeno tre spigoli, allora 3F sarà minore o uguale al numero totale di spigoli presenti nel grafo, moltiplicato per 2 (questo perché ogni spigolo confina con due facce, quindi viene contato due volte). In formule: 3F ≤ 2S.
Facciamo un po' di passaggi banali, come dicono i Veri Matematici.
F + V = S + 2 (formula di Eulero)
3F + 3V = 3S + 6 (moltiplico tutto per 3)
3S = 3F + 3V − 6 (ricavo 3S)
3S ≤ 2S + 3V − 6 (per quanto detto sopra, 3F ≤ 2S)
S ≤ 3V − 6 (sottraggo 2S a destra e a sinistra)
2S ≤ 6V − 12 (moltiplico tutto per 2).
Risultato: il doppio del numero di spigoli nel grafo è minore o uguale di 6V − 12.
Domanda: è possibile che ogni vertice sia connesso a almeno altri sei vertici? Se così fosse, il totale degli spigoli moltiplicati per 2 dovrebbe essere uguale a almeno 6V. Dato che 6V − 12 non può essere uguale a 6V, la risposta alla domanda è no.
Quindi esiste almeno un vertice connesso con altri cinque vertici al massimo.
Nel 1879 il matematico Alfred Kempe annunciò di aver dimostrato il teorema dei quattro colori. Solo undici anni dopo, nel 1890, Percy Heawood si accorse di un errore nella dimostrazione di Kempe. Nel farlo, notò il particolare di cui abbiamo discusso ora (e cioè che deve esistere almeno un vertice dal quale escono al più cinque spigoli) che aprì le porte alla dimostrazione del teorema dei cinque colori. Ovvero: cinque colori sono sufficienti per colorare una carta geografica.
Per dimostrarlo non servono né computer né pagine e pagine di dimostrazioni.
Nessun commento:
Posta un commento