Petersengraph in der projektiven Ebene
Als Erkennnungszeichen für den Tag der Mathematik haben wir in diesem Jahr den Petersen-Graphen in der projektiven Ebene gewählt.
Der Petersen-Graph wurde von Julius Petersen im Jahr 1898 als kleinster brückenloser kubischer Graph konstruiert, der mindestens vier Farben für eine minimale Kantenfärbung benötigt. Hierbei bedeutet brückenlos, dass die Wegnahme einer beliebigen Kante den Graphen nicht in zwei Teilgraphen trennt, und kubisch, dass wie beim Würfel an jeder Ecke genau drei Kanten eintreffen. Der Graph aus den Kanten eines Würfels ist z.B. auch brückenlos und kubisch, für eine Kantenfärbung genügen jedoch drei Farben.
So speziell die Charakterisierung des Petersen-Graphen erscheint, so hat er es in der Graphentheorie doch zu Popularität gebracht: als Beispiel und Gegenbeispiel für viele graphentheoretische Eigenschaften. So ist der Petersen-Graph der kleinste brückenlose kubische Graph, der keinen Hamiltonkreis besitzt. Andererseits ist er ein Beispiel für einen hypohamiltonischen Graph.
Lange Zeit (1898-1946) ist der Pertersen-Graph der einzige bekannte Snark-Graph gewesen, worunter man brückelnlose, kubische Graphen mit chromatischem Index 4 versteht. Und Snarks wiederum sind seit 1880 interessant, als Peter G. Tait bewies, dass das Vier-Farbenproblem äquivalent zur Eigenschaft ist, dass es keinen planaren Snark gibt. Jeder Snark in der Ebene muss also Überkreuzungen von Kanten haben. Der Würfel ist zwar brückelos, kubisch und planar, hat allerdings chromatischen Index 3 und ist damit kein Snark. Der Petersen-Graph ist der erste bekannte Snark und hat minimale Kreuzungszahl 2, ist also nicht eben und widerlegt die Behauptung damit nicht.
Mit freundlicher Genehmigung aus dem Buch:
Georg Glaeser und Konrad Polthier
Bilder der Mathematik
SpringerSpektrum 2. erw. Auflage 2014
www.bilder-der-mathematik.de
