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.