Primi elementi della teoria dei grafi

Un'ulteriore prova della non planarità di K₅ e di K_3,3

Un grafo semplice planare è detto massimale se l'aggiunta di un ulteriore spigolo provoca la perdita della planarità. Ad esempio, nel grafo in figura non è possibile aggiungere un altro spigolo e ottenere ancora un grafo semplice planare.

Non è difficile verificare che tutte le facce interne di un grafo semplice planare massimale sono limitate da tre spigoli e la faccia esterna, anche se è illimitata, ha per confine tre spigoli del grafo. Inoltre, se S è il numero degli spigoli e F è il numero delle facce e ogni faccia è limitata da tre spigoli e ogni spigolo è comune a due facce possiamo scrivere l'uguaglianza 3F = 2S.

Se le facce interne di un grafo semplice planare non sono tutte limitate da tre spigoli (non è massimale) allora invece dell'uguaglianza si ha la disuguaglianza 3F < 2S.

In generale, in un grafo semplice planare, con almeno una faccia triangolare, vale la relazione 3F ≤ 2S dove F è il numero delle facce e S è il numero degli spigoli.

Sappiamo che per un grafo planare vale la relazione di Eulero che possiamo esplicitare in funzione del numero delle facce:

F = S + 2 - V cioè 3F = 3S + 6 - 3V

E sostituendo nella disuguaglianza si ha:

3S + 6 - 3V ≤ 2S cioè S ≤ 3V - 6

In generale, in un grafo semplice planare con almeno una faccia triangolare il numero degli spigoli deve essere minore o uguale alla differenza tra il triplo del numero dei vertici e 6.

Cosa succede se il grafo semplice planare non ha alcuna faccia triangolare? Ad esempio, nel grafo planare del cubo tutte le facce sono quadrangolari.

Con gli stessi ragionamenti di prima dall'uguaglianza 4F = 2V possiamo passare alla disuguaglianza S ≤ 2V - 4.

In generale, in un grafo semplice planare che non ha alcuna faccia triangolare il numero degli spigoli deve essere minore o uguale alla differenza tra il doppio del numero dei vertici e 4.

Queste due regole generali permettono di affermare che i grafi K₅ e K_3,3 non possono essere planari. Infatti, il grafo K₅ ha 10 spigoli e 5 vertici e se applichiamo la relazione S ≤ 3V - 6 si ha:

10 ≤ 15 - 6

che è falsa. Il grafo K_3,3 non ha cicli triangolari e ha 9 spigoli e 6 vertici e se applichiamo la relazione S ≤ 2V - 4 si ha:

9 ≤ 12 - 4

che è falsa.