\(\begingroup\)

Ein 4-regulärer Streichholzgraph mit 114 Kanten

In diesem Artikel stelle ich (m)einen 4-regulären Streichholzgraphen mit 114 Kanten vor. Dieser Graph - siehe rechts - wurde von mir am 15. April 2016 entdeckt und erstmals hier auf dem Matheplaneten präsentiert. Er ist nach dem Harborth-Graphen mit 104 Kanten das nun zweitkleinste bekannte Beispiel eines 4-regulären Streichholzgraphen und unterbietet seinen Vorgänger - der diesen Rekord immerhin 30 Jahre hielt - um 6 Kanten. Zwischen beiden Graphen existieren ein paar interessante geometrische Zusammenhänge. Im Prinzip muss der alte Graph nur leicht verformt, in Teilgraphen zerlegt, etwas bearbeitet und neu zusammengesetzt werden. Wie und warum das funktioniert, zeige ich im Artikel.

Streichholzgraphen bezeichnet man planare Graphen, deren Kanten Einheitslänge besitzen und die sich nicht überschneiden. Regulär ist ein solcher Graph genau dann, wenn an jeden seiner Knoten gleich viele Kanten grenzen. Der Name Streichholzgraph rührt von dem Umstand her, dass man solche Graphen auch mit gleichlangen Streichhölzern auf einer flachen Oberfläche nachbilden kann. Eine besondere Herausforderung bei allen Arten von Streichholzgraphen ist stets, den kleinstmöglichen zu finden, der mit einer minimalen Anzahl an Kanten auskommt. Das folgende Bild zeigt die bis heute kleinsten bekannten n-regulären Streichholzgraphen für n = 1 bis 4.

Sascha Kurz, Rom Pinchasi[3]) offiziell veröffentlicht wurde. Die Geschichte dieses Beweises ist allerdings etwas unübersichtlich und beginnt bereits 1982 bei Aart Blokhuis (siehe Anmerkungen). Für n = 5 und n = 6 existieren aber unendliche n-reguläre Streichholzgraphen mit einer unbegrenzten Anzahl an Knoten und Kanten. Der kleinste bekannte 4-reguläre Streichholzgraph mit 52 Knoten und 104 Kanten wurde 1986 von Heiko Harborth vorgestellt und auch nach ihm benannt. Ob es noch mindestens einen kleineren 4-regulären Streichholzgraphen als den Harborth-Graphen gibt, ist nach wie vor ein offenes Problem. Doch selbst ein anderer Graph mit 104 Kanten wäre schon eine kleine Sensation. Dass ein 4-regulärer Streichholzgraph mindestens 20 Kanten besitzen muss, zeigten Kurz und Pinchasi in einem 2014 veröffentlichten Artikel. Leider fristen Streichholzgraphen in der Fachwelt bis heute ein eher stiefmütterliches Dasein. Das liegt wohl zum Teil darin begründet, dass die Thematik einerseits fast schon trivialer Natur ist, aber andererseits sich ihre mathematische Behandlung so extrem schwierig gestaltet. Es gibt in der mathematischen Landschaft wohl nicht viele vergleichbare Aufgabenstellungen, die selbst schon Kinder im Grundschulalter vollständig verstehen und auch praktisch behandeln können. Für mich macht aber gerade diese Ambivalenz den Reiz der Streichholzgraphen aus. Es würde mich freuen, wenn dieser Artikel dazu beiträgt auch andere für diese interessante und spannende Sache zu begeistern. Denn in Welt der Streichholzgraphen gibt es noch viel Neues zu entdecken.

geometrischen Graphentheorie zwischen starren und flexiblen Graphen. Dazu betrachten wir im Folgenden nur Graphen mit Knotengraden > 1. Ist ein Graph starr, so können seine Kanten nicht gegeneinander bewegt werden ohne sie von einem Knoten zu lösen. Ist ein Graph flexibel, so können Kanten und Knoten gegeneinander bewegt werden ohne seine Knotengrade zu verändern bzw. den Graphen zu zerstören. Es gilt daher: Ist ein planarer Einheitsdistanz-Graph verformbar, so ist er flexibel, ansonsten ist er starr. Das einfachste Beispiel eines starren Streichholzgraphen ist 2-regulär, besitzt drei Knoten und Kanten und hat die Form eines gleichseitigen Dreiecks. Das einfachste Beispiel eines flexiblen Streichholzgraphen ist ebenfalls 2-regulär, besitzt vier Knoten und Kanten und hat die Form eines Quadrats bzw. einer Raute. Auch wenn die Beweglichkeit eines flexiblen Streichholzgraphen flächenmäßig begrenzt ist, so sind doch innerhalb dieser Grenzen die Möglichkeiten unendlich groß und es existieren unendlich viele Form-Variationen von ihm. Dass auch der Harborth-Graph starr ist, wurde erstmalig 2006 durch Eberhard H.-A. Gerbracht gezeigt. Durch die von Gerbracht mit Hilfe eines Computeralgebrasystems ermittelten Minimalpolynome für die Koordinaten der Ecken des Harborth-Graphen ist die Existenz des Graphen dann auch (fast) vollständig mathematisch nachgewiesen. Es bleibt eigentlich nur noch der strikte Nachweis, dass jedes der Minimalpolynome auch eine reelle Nullstelle besitzt, die dann die jeweiligen Koordinaten ergeben.

Auch wenn man es diesem Graphen nicht sofort ansieht - er ist flexibel und kann stetig verformt werden. Diese Flexibilität liegt in seinen Teilgraphen begründet, die ebenfalls flexibel sind. Der Teilgraph besteht aus 7 Knoten und 10 Kanten. Der er nur Knoten vom Grad 2 und 4 besitzt, bezeichnet man ihn auch als (4,2)-regulären Graphen. Während der untere Teil aus drei gleichseitigen Dreiecken starr ist, ist der obere Teil, das Quadrat, flexibel. Der Teilgraph selbst ist also eine Kombination aus den beiden einfachsten Beispielen für starre und flexible Streichholzgraphen. Machen wir uns jetzt an die Konstruktion des neuen Graphen. Zunächst spiegeln wir den Teilgraphen an der grünen Gerade durch die Knoten P1 und P2. Danach verformen wir die beiden Quadrate zu Rauten, indem wir den Knoten P2 nach unten und rechts bewegen. Und zwar so, dass die rote Strecke zwischen den Knoten P3 und P4 genau 2 Kantenlängen misst. Der blaue Winkel zwischen der Spiegelgerade und der waagerechten Kante an P1 beträgt im linken Bild genau 75 Grad, im rechten Bild sind es ungefähr 67,76 Grad. Nun lassen sich je genau sechs von diesen gespiegelten doppelten Teilgraphen wieder zu einem großen 4-regulären Streichholzgraphen zusammenfügen. Das linke Bild zeigt die beiden so erzeugten Graphen im direkten Vergleich. Man kann gut erkennen, wie der rote Graph verformt wurde. Nur noch der starre Teil des untersten Teilgraphen aus 5 Knoten und 7 Kanten hat hier in beiden Graphen dieselbe Position. Im rechten Bild sehen wir nur den verformten Graphen, der jetzt logischer Weise nur noch eine 6-fache Rotationssymmetrie besitzt. Alle Kanten, die waagerecht erscheinen, sind auch wirklich waagerecht. Der Graph lässt sich natürlich noch viel extremer verformen, doch wir brauchen ihn für unsere Zwecke in genau dieser Form. Der neue Graph lässt sich auch in vier Viertel-Teilgraphen einteilen, die sich jeweils auf die gegenüberliegende Seite spiegeln lassen (Abb. a). Wir nehmen uns jetzt einen Viertel-Teilgraph heraus (Abb. b), und ziehen eine senkrechte Gerade durch den Knoten P5 und den Kantenmittelpunkt P6 (Abb. c). Nun löschen wir die neuneinhalb blauen Kanten und drehen die beiden roten Kanten an die senkrechte Gerade, auf der sie sich in Punkt P7 treffen (Abb. d). Die beiden Kanten zwischen den Knoten P8, P2 sowie P2, P7 besitzen exakt gleiche Winkel. Dasselbe gilt für die Kanten zwischen den Knoten P10, P9 und P9, P7. Die Kante zwischen den Knoten P11, P10 ist genau waagerecht bzw. parallel zur Kante zwischen den Knoten P1, P5. Der waagerechte Abstand des Knoten P2 zur senkrechten Gerade beträgt genau eine viertel Kantenlänge. Im nächsten Schritt spiegeln wir diese Figur an der senkrechten Gerade und erhalten einen neuen Teilgraphen aus 22 Knoten und 41 Kanten, den ich Triplet-Kite genannt habe (Abb. e). Der Triplet-Kite ist ein starrer Graph. Für die Starrheit ist der Knoten P7 verantwortlich. Dieser Graph besitzt eine ganz wunderbare geometrische Eigenschaft. Verbindet man nämlich die Kantenmittelpunkte P12 und P15, und konstruiert mit dieser Strecke ein gleichseitiges Dreieck, dann verlaufen die beiden Strecken P12, P16 und P15, P16 jeweils genau durch den Kantenmittelpunkt P13 bzw. P14 (Abb. f). Daraus folgt, dass sich drei Triplet-Kites so kombinieren lassen, dass ihre äußeren Dreiecke jeweils paarweise genau übereinander liegen, was uns schließlich zu unserem neuen minimalen 4-regulären Streichholzgraphen mit 114 Kanten führt (Abb. g). Der neue Graph besitzt noch eine weitere wunderbare geometrische Eigenschaft. Die drei mittleren Knoten besitzen nämlich zueinander genau eine Kantenlänge Abstand, so dass man mit einer bzw. drei zusätzlichen Kanten auch einen (4,5)-regulären bzw. (4,6)-regulären Streichholzgraphen konstruieren kann. Solche Graphen dürfen neben Knoten vom Grad 4 auch Knoten vom Grad 5 bzw. 6 besitzen. Mit ihren 115 bzw. 117 Kanten sind diese beiden Streichholzgraphen die zurzeit kleinsten bekannten Beispiele ihrer Art. Diese und weitere aktuelle Minimalitäts-Rekorde für (4,n)-reguläre Streichholzgraphen finden sich in diesem Artikel und auf dieser Website. Die beiden oberen Bilder zeigen den neuen roten Graphen im direkten Vergleich zu seinen 120-kantigen Vorgängern. Links mit der ursprünglichen und rechts mit der verformten Version. Die schwarzen Punkte kennzeichnen dabei Knoten, welche in beiden überlagerten Graphen identisch sind. Das untere linke Bild soll noch einmal die wunderschöne 3er-Symmetrie des neuen Graphen hervorheben, während ihn das rechte Bild mit zusätzlichen bunten Kanten zeigt. Diese grenzen entweder an die ursprünglichen Knoten oder an Kantenmittelpunkte. Das letzte Bild ist dem neuen Graphen in seiner reinsten Form gewidmet. Auch wenn es etwas kitschig klingt - ich empfinde für diesen Graphen wahre Liebe. Viele Grüße, Slash