Troppe facce!

Una mattina il mio amico Layos mi ha chiesto qual era la dimostrazione di un "semplice fatto" sui grafi planari che aveva trovato su un libro che stava leggendo: che la formula di Eulero implica che un grafo planare semplice con n vertici ha al più 3n-6 archi. (ammesso che n sia maggiore o uguale a 3... ma questo l'ho scoperto dopo). In effetti il fatto non è troppo difficile da provare, ma trovare una dimostrazione corretta mi ha fatto perdere un po' di tempo. Essendo io un pigrone, ho pensato che tanto valeva riscriverla qua, magari qualcuno è interessato a vedere una "dimostrazione a pezzi".

Un po' di definizioni prima di iniziare la dimostrazione vera e propria. Un grafo è una specie di rete: ci sono dei punti (i nodi) che sono connessi tra loro con delle linee (gli archi). Un grafo si dice planare se lo si può stendere su un piano senza che ci siano degli archi che si intersechino: ad esempio, un quadrato con le sue diagonali non sembrerebbe planare (le diagonali si incrociano) ma si può spostare una delle due diagonali all'esterno del quadrato, eliminando l'intersezione. Infine un grafo si dice semplice quando due nodi hanno al più un arco che li congiunge.

La formula di Eulero è poi quella che forse vi ricordate usando la frasetta mnemonica "Fatti Vedere Sabato alle due", che dovrebbe farvi tornare in mente la formula stessa:

[1]F + V = S + 2

dove F sono le facce di un poliedro, V i vertici e S gli spigoli. Nel nostro caso non abbiamo un poliedro ma un grafo, il che significa - dopo avere associato ai vertici i nodi, e agli spigoli gli archi - che la formula diventa

[2] F + V = S + 1

Questo perché possiamo supporre che la parte esterna del grafo sia una faccia del poliedro che è stata bucata e allargata per stendere il poliedro stesso sul piano e ottenere appunto un grafo.

[Figura 1: il grafo originario] Quello che dobbiamo dimostrare è che in un qualunque grafo planare semplice vale la formula [Figura 2: eliminiamo i segmenti solitari]

[3] S ≤ 3V - 6

Il trucco per la dimostrazione è partire da un grafo planare semplice qualunque, mostrato nella Figura 1, e convertirlo man mano in uno di forma più standard, assicurandoci che nelle trasformazioni la disuguaglianza resti vera; se cioè si fa crescere di n il lato sinistro della disuguaglianza, quello destro deve crescere di n o meno, mentre se si toglie n al lato sinistro, a quello destro bisogna togliere n o più.

Il primo passo da compiere, come mostrato nella Figura 2, è quello di eliminare gli "archi solitari", quelli cioè per cui per uno dei loro nodi parte un solo arco, e che pertanto ci impediscono di applicare la formula di Eulero :-) Se questi archi sono k, eliminarli riduce di k il valore a lato sinistro della [3] e di 3k il valore a lato destro; quindi se la formula vale per il nostro grafo ridotto, a maggior ragione valeva per il grafo originale. Non è detto che l'eliminazione possa avvenire in un solo colpo: nel nostro esempio pratico, infatti, occorrono due passi per eliminare tutti gli archi solitari.

[Figura 3: triangoliamo] Il passo successivo è mostrato nella Figura 3: partendo dal nostro grafo, ne costruiamo un altro dove tutte le "facce interne" (vale a dire i circuiti che non contengono al loro interno alcun arco) siano dei triangoli. Per fare questo, inseriamo nuovi archi che uniscano nodi già esistenti. Se una faccia interna al nostro grafo è un k-gono, aggiungendo opportunamente un arco otteniamo un triangolo e un (k-1)-gono, il che significa innanzitutto che possiamo completare la triangolazione della faccia con k-3 applicazioni successive; inoltre ciascuna applicazione lascia intatto il numero di nodi e aumenta di uno quello degli archi, il che significa che se la formula [3] vale per il nuovo grafo ottenuto dopo la triangolazione doveva valere anche per quello vecchio. Nella Figura 4 continuiamo la triangolazione, ma questa volta all'esterno del grafo stesso. Essendo il grafo planare, esso sta tutto all'interno di una curva chiusa abbastanza ampia. Possiamo allora rimpicciolire questa curva fino a che non tocca alcuni nodi e alcuni archi del grafo; questi sono appunto quelli esterni. [Figura 4: triangolazione esterna]

Aggiungiamo ora degli archi che uniscono tra loro due nodi esterni per cui ci sia un percorso che porti dal primo al secondo esattamente in due passaggi: in pratica stiamo di nuovo facendo dei triangoli, ma all'esterno del grafo. Di nuovo, queste aggiunte lasciano intatto il numero di nodi e aumentano il numero di archi, quindi se la formula [3] vale per il nuovo grafo varrà anche per il grafo iniziale; inoltre il numero di nodi all'esterno del grafo diminuisce di uno.

Continuando ad aggiungere archi esterni fino a che è possibile, otteniamo alla fine un grafo come quello in Figura 4. In questo grafo tutti gli archi fanno parte esattamente di due facce tranne i tre esterni: pertanto se noi moltiplichiamo per tre il numero di facce e sommiamo i tre archi esterni, abbiamo contato esattamente il doppio degli archi. In formule,

[4] 2S = 3F + 3

A questo punto ricaviamo F dalla [2] e sostituiamolo nella [4]: otteniamo così

[5] 2S = 3S + 3 - 3V + 3

[Figura 5: un controesempio] che spostando opportunamente i vari termini tra i due membri dell'uguaglianza diventa

[6] S = 3V - 6

che era quanto dovevamo dimostrare. (Il "minore o uguale" ce lo siamo persi nei vari passaggi dove abbiamo man mano fatto crescere il numero di archi senza toccare i vertici). Come corollario, abbiamo anche dimostrato quando si ha l'uguaglianza: non ci devono essere "archi solitari" né ci devono essere sottografi non triangolari.

Un'ultima nota. Se ricordate l'enunciato del teorema, il grafo non solo deve essere planare ma anche semplice. In caso contrario, è facilissimo trovare un controesempio: la Figura 5 mostra un grafo che ha solo due nodi, ma ben sei archi, e ovviamente il numero di archi può crescere a piacere.

Un controesempio al teorema nel caso il grafo sia semplice ma non planare è dato invece dal "pentagono completo", quello cioè disegnato con tutte le diagonali; esso ha 5 nodi e 10 archi, mentre la formula del teorema dà al più 9 archi.