Primi elementi della teoria dei grafi

Formula dei poliedri di Eulero

Per i poliedri convessi esiste una relazione che lega i numeri dei vertici, degli spigoli e delle facce scoperta da Eulero e detta in suo onore formula di Eulero:

In un poliedro convesso il numero dei vertici V più il numero delle facce F è sempre uguale al numero degli spigolo S più 2:

V + F = S + 2

Ad esempio, il poliedro convesso in figura

ha 12 vertici (V = 12), 14 facce (F = 14) e 24 spigoli (S = 24) e applicando la formula di Eulero si ha 12 + 14 = 24 + 2. Questa semplice relazione è sorprendente perchè vale per un'infinità di poliedri convessi e non ha importanza nè la forma delle facce nè la lunghezza degli spigoli nè la disposizione dei vertici. Ed ecco un'altra sorpresa, questa formula vale anche per un qualsiasi grafo poligonale. Abbiamo visto che lo scheletro di ogni poliedro convesso può essere rappresentato con un grafo poligonale facendo corrispondere ad ogni vertice e ad ogni spigolo del poliedro un vertice e uno spigolo del grafo ma possiamo anche far corrispondere ad ogni faccia del poliedro una faccia del grafo poligonale. Ad esempio un cubo ha 8 vertici, 12 spigoli e 6 facce, il corrispondente grafo poligonale ha 8 vertici, 12 spigoli e 6 facce dove la sesta faccia e quella esterna al contorno dell'intero grafo con tutte le sue facce ed è detta faccia infinita.

Naturalmente questa formula vale nel caso più semplice in cui il grafo poligonale è costituito da un solo poligono con n vertici, n spigoli e due facce una interna e l'altra esterna: n + 2 = n + 2. Ad esempio, il grafo poligonale in figura ha 6 vertici, 6 spigoli e 2 facce (quella interna e quella infinita).

Cosa succede se al grafo precedente aggiungiamo di volta in volta una nuova faccia collegata con i vertici e gli spigoli del grafo?

Per ogni faccia in più dobbiamo aggiungere n vertici e n+1 spigoli:

V+n + F+1 = S+n+1 + 2 e cioè V + F = S + 2

Come si vede sia a sinistra che a destra dell'uguaglianza viene aggiunto lo stesso numero n+1 e quindi continua a valere la relazione di Eulero. La formula di Eulero vale anche per i grafi planari connessi; in questo caso gli spigoli delle facce possono essere delle qualsiasi curve che non si intersecano con se stesse e una faccia può essere delimitata soltanto da due spigoli. Ad esempio, il grafo in figura ha 7 vertici, 11 spigoli e 6 facce e naturalmente vale la formula di Eulero.

Ogni poliedro regolare ha un poliedro duale: i vertici diventano facce, le facce diventano vertici, gli spigoli restano spigoli. La formula di Eulero rimane invariata nel passaggio al duale.