Petersen-Graph
Benannt nach	Julius Peter Christian Petersen
Größe	10 Knoten, 15 Kanten
Eigenschaften	snark, kubisch.
Chromatische Zahl	3
Chromatischer Index	4
Knotenzusammenhang	3
Cliquenzahl	2
Schnittzahl	2
Chromatisches Polynom	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-}$ ${\displaystyle 230t^{4}+529t^{3}-814t^{2}+775t-352)}$
Charakteristisches Polynom	${\displaystyle (t-1)^{5}(t+2)^{4}(t-3)}$
LCF-Notation	{{{LCF}}}

Der Petersen-Graph (benannt nach dem dänischen Mathematiker Julius Petersen) ist ein 3-regulärer (also kubischer) Graph mit 10 Knoten. Das bedeutet, dass jeder der Knoten drei Nachbarn hat, die Gradfolge ist also (3,3,3,3,3,3,3,3,3,3). Der Petersen-Graph ist in der Graphentheorie ein oft verwendetes Beispiel und Gegenbeispiel. Er tritt auch in der tropischen Geometrie auf.

Eigenschaften des Petersen-Graphen:

• Kubisch bzw. 3-regulär (per Definition)
• Radius und Durchmesser sind 2
• Geschlecht ist 1
• Nicht planar
• Zusammenhängend
• Symmetrisch
• Stark regulär
• Snark
• Die Länge des kürzesten Kreises ist 5
• Die Länge des längsten Kreises ist 9
• Enthält keinen Hamilton-Kreis
• Kleinster hypohamiltonscher Graph
• Ist ein Ramanujan-Graph
• Ist kein Cayley-Graph, obwohl er regulär und lokal-endlich ist.
• Ist ein Einheitsdistanz-Graph, da er eine Darstellung besitzt, bei der alle Kanten Einheitslänge haben.

Der Petersen-Graph hat eine chromatische Zahl von 3, d. h. die Knoten müssen mit mindestens 3 Farben gefärbt werden, sodass jeweils zwei benachbarte Knoten unterschiedliche Farben haben. Der chromatische Index ist 4, d. h. man benötigt mindestens 4 Farben um alle Kanten so einzufärben, dass die inzidente Kanten jedes Knoten paarweise verschiedene Farben haben. Da der Petersen-Graph brückenlos und kubisch ist, aber einen chromatischen Index von 4 besitzt, zählt der Petersen-Graph zu den sogenannten Snark-Graphen. Er ist der kleinste und von 1898 bis 1946 der einzige Graph, für den diese Eigenschaft nachgewiesen wurde^[1].

• Eric W. Weisstein: Petersen-Graph. In: MathWorld (englisch).

Commons: Petersen-Graph – Sammlung von Bildern, Videos und Audiodateien

1. ↑ Julius Petersen: Sur le théorème de Tait. In: L'Intermédiaire des Mathématiciens. Band 5, 1898, S. 225–227 (archive.org).