\(\begingroup\)

Der große Bruder des Harborth-Graphen

In diesem Artikel stelle ich einen neuen 4-regulären Streichholzgraphen mit 108 Kanten vor. Dieser Graph - siehe rechts - wurde von StefanVogel, haribo und mir als Team im Verlauf unseres Streichholzgraphen-Threads hier auf dem Matheplaneten entdeckt und auch erstmals präsentiert. Er ist nach dem sehr ähnlich aussehenden Harborth-Graphen mit 104 Kanten das neue zweitkleinste bekannte Beispiel eines 4-regulären Streichholzgraphen, und löst damit den erst kürzlich hier präsentierten Graphen mit 114 Kanten ab. Wie sich der neue Graph in wenigen Schritten aus dem Harborth-Graphen konstruieren lässt, und dass beide Graphen wirklich existieren, soll hier gezeigt werden.

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 ihre Länge zu ändern oder sie von einem Knoten zu lösen. Ist ein Graph flexibel, so können seine Kanten und Knoten gegeneinander bewegt werden ohne die Kantenlängen oder Knotengrade zu verändern. 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, folgt sofort aus einfachen geometrischen Überlgungen zur Beweglichkeit eines seiner Viertel-Teilgraphen. 2006 ermittelte Eberhard H.-A. Gerbracht erstmalig mit Hilfe eines Computeralgebrasystems die Minimalpolynome für die Koordinaten der Ecken des Harborth-Graphen. Die reellen Nullstellen dieser Minimalpolynome geben dann die jeweiligen Koordinaten der Knoten an. Für den Beweis der Existenz und der Starrheit des Harborth-Graphen ist diese komplizierte Betrachtung mit Polynomen allerdings nicht nötig.

Die folgende Sequenz zeigt diesen Verformungsvorgang in fünf Bildern bis zum Zusammenfall der sich annähernden Kanten und Knoten. Man beachte: Die violetten und gelben Linien stellen nur sich verändernde Abstände und keine Kanten des Graphen dar. Es lässt sich gut erkennen, wie die violette Strecke zwischen den Knoten 1a und 1b stetig länger wird, bis sie schließlich zwei Kantenlängen misst und mit der horizontalen Symmetrieachse zusammenfällt. Die gelbe Strecke zwischen den Knoten 1a und 2a liegt zu Anfang auf der vertikalen Symmetrieachse und wird stetig kürzer, bis ihre Länge gleich Null ist und sie mit dem Knoten 4 zusammenfällt. Wie lässt sich aber so die Existenz des Harborth-Graphen beweisen? Nun, wir können uns diesen Verformungsprozess jetzt rückwärts denken, indem wir den Rautenblock in Abb. 5 stetig auseinander ziehen, so dass wir einen (4,2)-regulären Graphen wie in Abb. 4 erhalten. Wegen der zweifachen Spiegelsymmetrie des Graphen, kann dieser stetig derart verformt werden, dass die Knoten 3, 4, 5, 6, sowie die Knoten 7 und 8 jeweils auf einer der sich rechtwinklig schneidenden Symmetrieachsen liegen, und die Knoten 1a und 1b, 2a und 2b, 1a und 2a, sowie 1b und 2b jeweils paarweise auf parallelen Geraden dazu liegen (Abb. links). Dies beweist, dass es möglich ist den Graphen genau so zu verformen, dass die Knoten 1a und 1b, sowie 2a und 2b jeweils in einem Punkt auf der vertikalen Symmetrieachse zusammenfallen (Abb. rechts). Der blaue Winkel beträgt dann ca. 18,57431690427 Grad. Aus dieser Betrachtung folgt auch sofort die Starrheit des Graphen.

Der so entstandene (4,2)-reguläre Graph (Abb. 3 und 4) besitzt immer noch eine doppelte Spiegelsymmetrie. Um die Existenz des neuen 4-regulären Streichholzgraphen mit 108 Kanten (Abb. 5) zu beweisen, können wir daher dieselbe Methode anwenden, die wir zuvor beim Harborth-Graphen benutzt haben. Auch hier liegen die vier Knoten vom Grad 2 jeweils paarweise auf einer parallelen Gerade zu den sich rechtwinklig schneidenden Symmetrieachsen. Der einzige Unterschied besteht darin, dass die Knoten vom Grad 2 hier jeweils paarweise auf der horizontalen Symmetrieachse zusammenfallen. Der blaue Winkel misst dann ca. 20,13345437742 Grad. Genau wie der Harborth-Graph ist auch dieser Graph starr. Zum Abschluss der neue 4-reguläre Streichholzgraph mit 108 Kanten im Großformat.

Thread auch jeder für sich selbst nachvollziehen und beurteilen kann. Wir sind uns auf jeden Fall einig darüber, diesen Graphen gemeinsam entdeckt zu haben. Genau genommen beginnt die Geschichte des Graphen mit meinem Start des Threads am 17. Februar 2016, an dem sich haribo sofort mit großem Interesse beteiligte. Am 22. Februar schwenkte der Thread zu 4/n-regulären Streichholzgraphen um. Am 13. März kam dann StefanVogel dazu und half uns bei Prüfung und Berechnung der Geometrien neuer Graphen mit seiner selbst geschriebenen Software (siehe Anmerkungen). Am 30. März hat haribo zusammen mit einem Freund zum ersten Mal versucht den Harborth-Graphen zu modifizieren. Inzwischen hatten wir schon einige neue Minimalitätsrekorde zu den 4/n-regulären Streichholzgraphen aufgestellt. Am 21. April postete ich einige neue Ideen zu modifizierten Harborth-Graphen, die von Stefan überprüft wurden. Darauf aufbauend stellte Stefan am 24. April zum ersten Mal hier eine eigene Idee vor, die auch zum ersten Mal den neuen Graphen zeigt. Da Stefan den Graphen aber als nicht möglich getestet hatte, kümmerte sich keiner von uns weiter darum. Die Idee zu diesem Graphen geriet in Vergessenheit. Am 27. Juni passierte dann etwas sehr Kurioses. Ich poste hier um ca. 5:30 Uhr morgens zwei vermeintlich neue Ideen für modifizierte Harborth-Graphen. Da die Ideen aber relativ einfach sind, bin ich den gesamten Thread noch einmal durchgegangen, um zu sehen, ob wir sie nicht doch schon einmal hatten. Nachdem ich Stefans früheren Beitrag gesehen hatte, habe ich meinen Beitrag gleich wieder gelöscht. Zum Glück war aber auch haribo gerade online und hatte meinen kurzen neuen Post mit den Graphen gesehen. Da auch er Stefans alten Beitrag nicht mehr im Gedächtnis hatte, hat er meinen vermeintlich neuen Graphen geprüft und im Gegensatz zu Stefan für möglich gehalten. Einige Tage und Beiträge später, am 3. Juli, waren wir drei uns dann absolut sicher, dass dieser neue Graph wirklich existiert, und Stefan in seinem ersten Test ein Fehler unterlaufen war. Man sieht, hätte auch nur ein Glied in dieser Kausalitätskette gefehlt - der neue Graph wäre wohl bis heute unentdeckt geblieben. Ende gut - Graph gut. Viele Grüße, Slash