Nel campo matematico della teoria dei grafi, il grafo di Heawood è un grafo non orientato con 14 vertici e 21 spigoli, che prende nome da Percy John Heawood.^[1]

Il grafo di Heawood è cubico (ossia tutti i suoi vertici hanno grado 3) e tutti i cicli nel grafo hanno 6 o più spigoli. Ogni grafo cubico più piccolo ha cicli più brevi, dunque questo grafo è la gabbia 6, il più piccolo grafo cubico di calibro 6. È un grafo transitivo sulla distanza (vedi il censimento di Foster) e perciò regolare sulla distanza.^[2]

Ci sono 24 matching perfetti nel grafo di Heawood; per ogni matching, l'insieme degli spigoli non nel matching forma un ciclo hamiltoniano. Ad esempio, la figura mostra i vertici di questo grafo posto su un ciclo, con le diagonali interne del ciclo che formano un matching. Suddividendo gli spigoli del ciclo in due matching, possiamo ripartire il grafo di Heawood in tre matching perfetti (cioè, 3-colorare i suoi spigoli) in otto modi diversi.^[2] Ogni due matching perfetti, e ogni due cicli hamiltoniani, possono essere trasformati l'uno nell'altro da una simmetria del grafo.^[3]

Ci sono 28 cicli con sei vertici nel grafo di Heawood. Ogni ciclo 6 è disgiunto esattamente da altri tre cicli 6; tra questi tre cicli 6, ciascuno è la differenza simmetrica degli altri due. Il grafo con un solo nodo per ciclo 6, ed un solo spigolo per ogni coppia disgiunta di cicli 6, è il grafo di Coxeter.^[4]

Il grafo di Heawood è un grafo toroidale; cioè può essere immerso senza incroci in un toro. Un'immersione di questo tipo pone i suoi vertici e spigoli nello spazio euclideo tridimensionale come l'insieme dei vertici e degli spigoli di un poliedro non convesso con la topologia di un toro, il poliedro di Szilassi.

Il grafo prende il nome di Percy John Heawood, che nel 1890 provò che in ogni suddivisione del toro in poligoni, le regioni poligonali possono essere colorate al massimo da sette colori.^[5][6] Il grafo di Heawood forma una suddivisione del toro con sette regioni mutuamente adiacenti, mostrando che questo legame è stretto.

Il grafo di Heawood è anche il grafo di Levi dal piano di Fano, il grafo che rappresenta le incidenze tra i punti e le linee in quella geometria. Con questa interpretazione, i cicli 6 nel grafo di Heawood corrispondono ai triangoli del piano di Fano.

Il grafo di Heawood ha il numero di incroci 3, e questo è il più piccolo grafo cubico con quel numero di incroci^[7]. Incluso il grafo di Heawood, ci sono 8 distinti grafi di ordine 14 con numero di incroci 3.

Il grafo di Heawood è un grafo a distanza unitaria: può essere immerso nel piano in modo tale che i vertici adiacenti sono esattamente a distanza di uno, senza due vertici immersi nello stesso punto e nessun vertice immerso in un punto all'interno di uno spigolo. Tuttavia le immersioni conosciute di questo tipo mancano di una qualsiasi delle simmetrie che sono intrinseche nel grafo.^[8]

Il gruppo di automorfismo del grafo di Heawood è isomorfico rispetto al gruppo lineare proiettivo PGL₂(7), un gruppo di ordine 336.^[9] Esso, agisce transitivamente sui vertici, sugli spigoli e sugli archi del grafo. Perciò il grafo di Heawood è un grafo simmetrico. Esso ha automorfismi che portano un qualsiasi vertice a un qualsiasi altro vertice e un qualsiasi spigolo a un qualsiasi altro spigolo. Secondo il censimento di Foster, il grafo di Heawood, citato come F014A, è l'unico grafo simmetrico cubico su 14 vertici.^[10][11]

Il polinomio caratteristico del grafo di Heawood è ${\displaystyle (x-3)(x+3)(x^{2}-2)^{6}}$. È l'unico grafo con questo polinomio caratteristico, che lo rende un grado determinato dal suo spettro.

• 
  Il poliedro di Szilassi.
• 
  Il grafo di Heawood ha numero di incroci 3.
• 
  L'indice cromatico del grafo di Heawood è 3.
• 
  Il numero cromatico del grafo di Heawood è 2.
• 
  Un'immersione del grafo di Heawood in un toro (mostrata come un quadrato con condizioni periodiche al contorno) che lo ripartisce in sette regioni mutuamente adiacenti.

• Wikimedia Commons contiene immagini o altri file su Grafo di Heawood

• (EN) Eric W. Weisstein, Grafo di Heawood, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica