Petersen-grafen

Petersen-grafen er en kubisk graf med ti hjørner, oppkalt etter den danske matematikeren Julius Petersen, som først publiserte denne grafen i 1898. Petersen-grafen er et mye brukt eksempel og moteksempel i matematikk, siden den har mange interessante egenskaper.

Petersen-grafen har blant annet følgende egenskaper:
 Den er kubisk, det vil si 3-regulær.
 Den er ikke planar.
 Den er sammenhengende.
 Den korteste sykelen har lengde 5.
 Den har kromatisk tall 3, og kromatisk indeks 4.
 Den har en hamiltonsk sti, men ingen hamiltonsk sykel.
 Den har radius og diameter 2.

Grafteori