Grafo di Petersen
# Grafo di Petersen

Nel campo matematico della teoria dei grafi, il grafo di Petersen è un grafo non orientato con 10 vertici e 15 spigoli. È un piccolo grafo che serve come utile esempio e controesempio per molti problemi di teoria dei grafi. Il grafo di Petersen prende il nome da Julius Petersen, che nel 1898 lo costruì per essere il più piccolo grafo cubico privo di ponti senza nessuna colorazione dei tre spigoli.

Sebbene il grafo sia generalmente attribuito a Petersen, esso era apparso in realtà 12 anni prima, in un saggio di A. B. Kempe (1886). Kempe osservò che i suoi vertici possono rappresentare le dieci linee della configurazione di Desargues, e che i suoi spigoli rappresentano coppie di linee che non s'incontrano in uno dei dieci punti della configurazione.

Donald Knuth afferma che il grafo di Petersen è "una notevole configurazione che serve da controesempio a molte previsioni ottimistiche su ciò che potrebbe essere vero per i grafi in generale".

## Costruzioni

Il grafo di Petersen è il complemento del grafo lineare di $K_{5}$. Esso è anche il grafo di Kneser $KG_{5,2}$; questo significa che ha un solo vertice per ciascun sottoinsieme di 2 elementi di un insieme di 5 elementi, e due vertici sono collegati da uno spigolo se e solo se i sottoinsiemi corrispondenti di 2 elementi sono disgiunti l'uno dall'altro. Come grafo di Kneser della forma $KG_{2n-1,n-1}$ è un esempio di grafo dispari.

Geometricamente, il grafo di Petersen è il grafo formato dai vertici e dagli spigoli dell'emidodecaedro, cioè, un dodecaedro con punti, linee e facce opposte identificate insieme.

## Incorporazioni

Il grafo di Petersen è non planare. Qualsiasi grafo non planare ha come minori o il grafo completo $K_{5}$, o il grafo bipartito completo $K_{3,3}$, ma il grafo di Petersen ha entrambi come minori. Il minore $K_{5}$ può essere formato contraendo gli spigoli di un abbinamento perfetto, per esempio per i cinque spigoli corti della prima figura. Il minore $K_{3,3}$ può essere formato cancellando un vertice (per esempio il vertice centrale del disegno 3-simmetrico) e contraendo uno spigolo incidente a ciascun vicino del vertice cancellato.

Il disegno planare più comune e simmetrico del grafo di Petersen, come un pentagramma dentro un pentagono, ha cinque incroci. Tuttavia, questo non è il disegno migliore per minimizzare gli incroci; esiste un altro disegno (mostrato nella figura) con solo due incroci. Così, il grafo di Petersen ha numero di incroci 2. Su un toro il grafo di Petersen può essere disegnato senza gli incroci degli spigoli; esso perciò ha genere orientabile 1.

Il grafo di Petersen può anche essere disegnato (con gli incroci) nel piano in modo tale che tutti gli spigoli abbiano uguale lunghezza. Cioè, è un grafo a distanza unitaria.

La più semplice superficie non orientabile sulla quale il grafo di Petersen può essere incorporato senza incroci è il piano proiettivo. Questa è l'incorporazione data dalla costruzione a emidodecaedro del grafo di Petersen. L'incorporazione del piano proiettivo può anche essere formata dal normale disegno pentagonale del grafo di Petersen ponendo un cross-cap dentro la stella a cinque punte al centro del disegno, e indirizzando gli spigoli della stella attraverso questo cross-cap; il disegno risultante ha sei facce pentagonali. Questa costruzione forma una mappa regolare e mostra che il grafo di Petersen ha genere non orientabile 1.

## Simmetrie

Il grafo di Petersen è fortemente regolare (con firma srg(10,3,0,1)). È anche simmetrico, che significa che è transitivo sugli spigoli e transitivo sui vertici. Più nettamente, è 3-transitivo sugli archi: ogni cammino orientato con tre spigoli nel grafo di the Petersen può essere trasformato in ogni altro cammino di questo tipo mediante una simmetria del grafo. È uno dei soli 13 grafi cubici con distanze regolari.

Il gruppo di automorfismo del grafo di Petersen è il gruppo simmetrico $S_{5}$; l'azione di $S_{5}$ sul grafo di Petersen segue dalla sua costruzione come grafo di Kneser. Ogni omomorfismo del grafo di Petersen su sé stesso che non identifica i vertici adiacenti è un automorfismo. Come mostrato nelle figure, i disegni del grafo di Petersen possono esibire una simmetria a cinque vie o a tre vie, ma non è possibile disegnare il grafo di Petersen nel piano in modo tale che il disegno esibisce il gruppo di simmetria piena del grafo.

Malgrado il suo alto grado di simmetria, il grafo di Petersen non è un grafo di Cayley. È il più piccolo grafico transitivo sui vertici che non sia un grafo di Cayley.

## Cammini e cicli hamiltoniani

Il grafo di Petersen ha un cammino hamiltoniano ma nessun ciclo hamiltoniano. È il più piccolo grafo cubico privo di ponti senza cicli hamiltoniani. È ipohamiltoniano, che significa che sebbene non abbia cicli hamiltoniani, cancellare un qualsiasi vertice lo rende hamiltoniano, e in questo ambito è il più piccolo grafo ipohamiltoniano.

Come grafo finito connesso transitivo sui vertici che non ha un ciclo hamiltoniano, il grafo di Petersen è un controesempio di una variante della congettura di Lovász, ma la formulazione canonica della congettura richiede un cammino hamiltoniano ed è verificata dal grafo di Petersen.

Sono noti solo cinque grafi connessi transitivi sui vertici senza cicli hamiltoniani: il grafo completo $K_2,$ il grafo di Petersen, il grafo di Coxeter e due grafi derivati dai grafi di Petersen e Coxeter sostituendo ciascun vertice con un triangolo. Se G è un grafo 2-connesso, r-regolare con al massimo 3r + 1 vertici, allora o G è hamiltoniano o è il grafo di Petersen.

Per vedere che il grafo di Petersen non ha un ciclo hamiltoniano C, descriviamo i grafi 3-regolari a dieci vertici che hanno effettivamente un ciclo hamiltoniano e mostriamo che nessuno di essi è il grafo di Petersen, trovando in ciascuno di essi un ciclo che è più breve di qualsiasi ciclo nel grafo di Petersen. Qualsiasi grafo 3-regolare hamiltoniano a dieci vertici consiste in un ciclo C a dieci vertici più cinque corde. Se una qualsiasi corda collega due vertici a distanza due o tre l'uno dall'altro lungo C, il grafo ha un 3-ciclo o 4-ciclo, e perciò non può essere un grafo di Petersen. Se due corde collegano due vertici opposti di C a vertici a distanza quattro lungo C, c'è di nuovo un 4-ciclo. Il solo caso rimanente è una scala di Möbius formata collegando ciascuna coppia di vertici opposti mediante una corda, che ha ancora un 4-ciclo. Poiché il grafo di Petersen ha calibro cinque, non può essere formata in questo modo e non ha un ciclo hamiltoniano.

## Colorazione

Il grafo di Petersen ha numero cromatico 3, che significa che i suoi vertici possono essere colorati con tre colori — ma non con due — in modo tale che nessuno spigolo colleghi vertici dello stesso colore.

Il grafo di Petersen ha indice cromatico 4; la colorazione degli spigoli richiede quattro colori. Una prova di ciò richiede il controllo di quattro casi per dimostrare che non esiste alcuna 3-colorazione degli spigoli. In quanto grafo cubico connesso privo di ponti con indice cromatico quattro, il grafo di Petersen è uno snark. È il più piccolo snark possibile, e fu l'unico snark conosciuto dal 1898 fino al 1946. Il teorema degli snark, un risultato congetturato da W. T. Tutte e annunciato nel 2001 da Robertson, Sanders, Seymour e Thomas, afferma che ogni snark ha il grafo di Petersen come minore.

In aggiunta, il grafo ha indice cromatico frazionario 3, provando che la differenza tra l'indice cromatico e l'indice cromatico frazionario può essere pari a 1. La congettura di Goldberg-Seymour, che resiste da lungo tempo, propone che questo sia il massimo divario possibile.

Il numero di Thue (una variante dell'indice cromatico) del grafo di Petersen è 5.

## Altre proprietà

Il grafo di Petersen:

* è 3-connesso e quindi 3-connesso sugli spigoli e privo di ponti. Vedi il glossario.
* ha numero d'indipendenza 4 ed è 3-partito. Vedi il glossario.
* è cubico, ha numero di dominio 3, e ha un abbinamento e un 2-fattore.
* ha 6 distinti abbinamenti perfetti.
* è il più piccolo grafo cubico di calibro 5. (È l'unico $(3,5)$-gabbia. In realtà, poiché ha solo 10 vertici, è l'unico $(3,5)$-grafo di Moore.)
* ha raggio 2 e diametro 2. È il più grande grafo cubico con diametro 2.
* ha spettro dei grafi −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
* ha 2000 alberi ricoprenti, il numero più alto di qualsiasi grafo cubico con 10 vertici.
* ha polinomio cromatico $t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right).$
* ha polinomio caratteristico $(t-1)^{5}(t+2)^{4}(t-3)$, che ne fa un grafo integrale—un grafo il cui spettro consiste completamente di numeri interi.

## Congettura della colorazione di Petersen

Secondo DeVos, Nesetril e Raspaud, "Un ciclo di un grafo G è un insieme C $\subseteq$ E(G) tale che ogni vertice del grafo (V(G),C) ha grado pari. Se G, H sono grafi, definiamo una mappa φ: E(G) → E(H) ciclo-continua se la pre-immagine di ogni ciclo di H è un ciclo di G. Una congettura affascinante di Jaeger asserisce che ogni grafo privo di ponti ha una mappatura ciclo-continua al grafo di Petersen. Jaeger mostrò che se questa congettura è vera, allora lo sono anche la congettura della doppia copertura di 5-ciclo e la congettura di Berge-Fulkerson."

## Grafi correlati

Il grafo di Petersen generalizzato G(n,k) è formato connettendo i vertici di un n-gono regolare ai vertici corrispondenti di un poligono a stella con simbolo di Schläfli {n/k}. Per esempio, in questa notazione, il grafo di Petersen graph è G(5,2): esso può essere formato connettendo i vertici corrispondenti di un pentagono e di una stella a cinque punte, e gli spigoli della stella connettono ogni secondo vertice. I grafi generalizzati di Petersen includono anche l'n-prisma G(n,1), il grafo di Dürer G(6,2), il grafo di Möbius-Kantor G(8,3), il dodecaedro G(10,2), il grafo di Desargues G(10,3) e il grafo di Nauru G(12,5).

The famiglia di Petersen consiste dei sette grafi che possono essere formati dal grafo di Petersen mediante zero o più applicazioni of trasformazioni Δ-Y o Y-Δ. Anche il grafo completo $K_6$ è nella famiglia di Petersen. Questi grafi formano i minori proibiti per grafi incorporabili senza collegamenti, grafi che possono essere incorporati nello spazio tridimensionale in modo tale che nessuna coppia di cicli nel grafo sia collegata.

Il grafo di Clebsch contiene molte copie del grafo di Petersen come sottografi indotti: per ciascun vertice v del grafo di Clebsch, i dieci nin vicini di v inducono una copia del grafo di Petersen.

