Petersen Graph Petersen-Graph
The smallest bridgeless cubic graph without a perfect matching Der kleinste brückenlose kubische Graph ohne perfektes Matching
The Petersen graph, introduced by Julius Petersen in 1898, is one of the most celebrated graphs in combinatorics. It serves as a counterexample to many conjectures and as a test case for graph-theoretic theorems.
It is a 3-regular (cubic) graph: every vertex has exactly three neighbours. Despite its high symmetry — any vertex can be mapped to any other by an automorphism — it has no Hamiltonian cycle, making it a classic counterexample in graph theory.
The model shows the graph embedded in 3-space with vertices as small spheres and edges as cylinders. The two natural parts of the graph — the outer pentagon and the inner pentagram — are highlighted in different colours.
Der Petersen-Graph, eingeführt von Julius Petersen im Jahr 1898, ist einer der bekanntesten Graphen der Kombinatorik. Er dient als Gegenbeispiel zu vielen Vermutungen und als Testfall für graphentheoretische Sätze.
Er ist ein 3-regulärer (kubischer) Graph: Jeder Knoten hat genau drei Nachbarn. Trotz seiner hohen Symmetrie — jeder Knoten kann durch einen Automorphismus auf jeden anderen abgebildet werden — besitzt er keinen Hamiltonkreis, was ihn zu einem klassischen Gegenbeispiel in der Graphentheorie macht.
Das Modell zeigt den Graphen eingebettet in den 3-dimensionalen Raum, mit Knoten als kleine Kugeln und Kanten als Zylinder. Die beiden natürlichen Teile des Graphen — das äußere Pentagon und der innere Pentagramm — sind in verschiedenen Farben hervorgehoben.
Properties Eigenschaften
- Vertices Knoten
- 10
- Edges Kanten
- 15
- Regularity Regularität
- 3-regular (cubic)
- Girth Taillenweite
- 5
- Diameter Durchmesser
- 2
- Chromatic number Chromatische Zahl
- 3
- Hamiltonian Hamiltonsch
- No / Nein
Further Reading Weiterführende Literatur
- Petersen, J. (1898). Sur le théorème de Tait. L'Intermédiaire des Mathématiciens, 5, 225–227.
- Petersen graph — Wikipedia
- Holton, D. A., & Sheehan, J. (1993). The Petersen Graph. Cambridge University Press.