Graf Petersena

Graf Petersena to graf o ciekawych własnościach często używany w teorii grafów. Nazwa pochodzi od nazwiska matematyka J. Petersena, któremu przypisuje się pierwszą publikację na temat grafu w 1898 roku.

• 
  Graf Petersena
• 
  Graf Petersena narysowany z dwoma przecięciami.
• 
  Graf Petersena narysowany tak, że wszystkie krawędzie są tej samej długości.

Własności

Graf Petersena...

• jest silnie regularny stopnia 3.
• jest trójspójny i trójspójny krawędziowo.
• ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
• jest grafem trójdzielnym.
• jest dopełnieniem grafu krawędziowego grafu K₅.
• jest symetryczny, to znaczy krawędziowo tranzytywny i wierzchołkowo tranzytywny.
• nie jest grafem planarnym.

Własności grafu Petersena:

liczba wierzchołków	10
liczba krawędzi	15
Stopień	3
liczba chromatyczna	3
indeks chromatyczny	4
promień	2
średnica	2
obwód	5
widmo	−2, −2, −2, −2, 1, 1, 1, 1, 1, 3

Inne cechy

• jest najmniejszym żmirłaczem.
• jest najmniejszym grafem kubicznym bez mostów i cykli Hamiltona.
• jest największym grafem kubicznym o średnicy 2.
• jest najmniejszym grafem hipohamiltonowskim.