\(\begingroup\)

Mit Dreiecken aus Pappe scheint die Aufgabe klar. Ein Graphentheoretiker möchte jedoch auch den Spezialfall ausschließen bei dem Ecken genau auf Kanten liegen, denn nur so ist der Graph planar. Er sucht daher nach einem Existenzbeweis bzw. der minimalsten Knotenzahl eines 4-regulären planaren Einheitsdistanz-Graphen, dessen Knoten keine 180 Grad Winkel zwischen zwei Kanten besitzen. Ein planarer Einheitsdistanz-Graph wird auch Streichholzgraph genannt. Die Fragestellung geht zurück auf eine Arbeit von Heiko Harborth aus dem Jahr 1991 [1] und war seitdem ein offenes Problem. Lässt man auch größere Dreiecke bzw. 180 Grad Winkel an den Knoten zu, finden sich schnell zwei Lösungen mit je 42 Einheits-Dreiecken (Abb. 1). Das Dreieck \((A, B, C)\) zeigt eines der größeren Dreiecke.

Die Graphen in Abbildung 1 sind beide starr, können also nicht verformt werden wie z.B. eine Raute. Ob es noch weitere Lösungen mit 42 Einheits-Dreiecken oder sogar einer geringeren Anzahl gibt, ist nicht bekannt. Es ist zwar sehr unwahrscheinlich, doch einen Beweis dafür gibt es bislang nicht. Harborth zeigte in seiner Arbeit auch, dass mindestens 3800 Einheits-Dreiecke nötig sind, wenn man erlaubt, dass Ecken auch auf Kanten liegen dürfen. Er konstruierte dazu den starren Teilgraphen \(G_1\), der aus 38 Einheits-Dreiecken besteht und spiegelsymmetrisch zur Geraden \(BE\) ist (Abb. 2). 100 Kopien dieses Teilgraphen lassen sich zu einem 4-regulären Ring-Graphen verbinden (Abb. 3). Dieser Ring ist, wie auch \(G_1\) selbst, nicht-planar und starr. Beweise der Existenz und Nicht-Planarität von \(G_1\) und des Ring-Graphen finden sich hier [1].

Um das Problem zu lösen, muss das Rad bzw. der Graph nicht neu erfunden werden. Ein geschickte Modifikation des Teilgraphen \(G_1\) genügt. Durch eine Veränderung der rechten Seite wird der neue Teilgraph \(G_2\) flexibel, und diese Beweglichkeit ist der Schlüssel zur Planarität (Abb. 4). Da diese Idee nicht von mir stammt, darf ich mit Recht behaupten, dass sie ganz schön raffiniert ist - einfach, aber genial. Auch \(G_2\) ist spiegelsymmetrisch zur Geraden \(BE\). In den Zoom-Kästchen sieht man gut, wie sich durch die Modifizierung die oberen und unteren Knoten der Rauten von den Dreieckskanten lösen. Die Rauten sind jedoch weiterhin so schmal, dass der Abstand \(\overline{GH}\) in dieser Auflösung nicht zu erkennen ist. Die Tabelle in Abbildung 5 zeigt eine Übersicht der approximierten Werte der Winkel und Distanzen beider Teilgraphen.

Satz: Es werden mindestens 6422 Einheits-Dreiecke benötigt, um einen 4-regulären planaren Einheitsdistanz-Graphen zu konstruieren, der keine größeren Dreiecke enthält.

Beweis: Wir arrangieren 38 Einheits-Dreiecke so in der Ebene, dass wir den Teilgraphen \(G_2\) erhalten. Dieser besitzt (wie auch \(G_1\)) nur Knoten der Grade 2 und 4. Die 2-gradigen Knoten liegen dabei exakt auf den Geraden \(g_{1}\) und \(g_{2}\), welche sich rechts von \(E\) schneiden. \(G_2\) ist flexibel und spiegelsymmetrisch zur Geraden \(BE\). Sei \(n\) eine ganze Zahl und \(\frac{360^\circ}{n}\) der Schnittwinkel zwischen \(g_{1}\) und \(g_{2}\). Stellen wir uns jetzt die beiden Geraden als Schienen vor, auf denen die 2-gradigen Knoten mit Ausnahme von \(D\) und \(F\) beweglich gelagert sind. \(D\) und \(F\) werden dabei ganz aus der Schienenführung herausgenommen und können sich frei in alle Richtungen über die Schienen bewegen. Wegen seiner Flexibilität können wir den Teilgraphen \(G_2\) nun geringfügig auf den Schienen hin- und herschieben, wobei sich \(D\) und \(F\) auf und ab bewegen. Bei einer solchen Bewegung bleibt kein Winkel in \(G_2\) konstant. Wird nun einer der Winkel \(\alpha\), \(\beta\), oder \(\gamma\) kontinuierlich ein wenig um seinen Wert aus der Tabelle in Abbildung 5 verändert, dann schneidet die Bahn von \(D\) bzw. \(F\) irgendwann \(g_{2}\) bzw. \(g_{1}\). Diese Schnittpunkte lassen sich nicht genau angeben, doch sie müssen existieren. Während dieser Bewegung muss sichergestellt werden, dass kein Knoten vom Grad 4 eine andere Kante oder eine der Geraden schneidet. Das kleineste \(n\) für das dies möglich ist, ist \(n=169\). Aufgrund der Spiegelsymmetrie von \(G_2\) können wir nun 169 Kopien dieses Teilgraphen so zu einem Ring zusammenfügen, dass die 2-gradigen Knoten \(A\) und \(C\), sowie \(F\) und \(D\) jeweils paarweise zu 4-gradigen Knoten zusammenfallen (Abb. 6). So erhalten wir einen 4-regulären planaren Ring-Graphen aus \(169\cdot38=6422\) Einheits-Dreiecken, der keine größeren Dreiecke besitzt. Dieser Ring-Graph ist starr. Sein Mittelpunkt ist der Schnittpunkt der Geraden \(g_{1}\) und \(g_{2}\).\(\square\)

Der Existenzbeweis des Ring-Graphen aus dem Harborth-Teilgraphen \(G_1\) ist sogar etwas einfacher, da er starr ist und sich die Geraden \(g_{1}\) und \(g_{2}\) in einem Winkel von genau 3,6 Grad schneiden. Einen Größenvergleich beider Ring-Graphen kann man sich hier ansehen.

Es existiert auch ein planarer 4-regulärer Einheits-Dreieck-Graph mit 100-facher Rotations- symmetrie. Dieser Ring-Graph besteht aus 9200 Einheits-Dreiecken und wird mit Kopien des Teilgraphen \(G_3\) konstruiert (Abb. 7). Auch \(G_3\) besitzt sehr geringe Abstände zwischen Knoten und Kanten. Ohne Computerunterstützung wäre die Berechnung der Teilgraphen \(G_2\) und \(G_3\) nicht möglich gewesen [3]. Herr Harborth hingegen kam noch mit Papier und Bleistift aus.

Eine schwierige und noch offene Frage ist, ob 4-reguläre planare Graphen aus Einheits-Dreiecken ohne größere Dreiecke auch noch in anderen Formen außer Ringen existieren können. Für nicht-planare Exemplare wurde bereits eine Antwort gefunden. In \(G_1\) liegen die Knoten auf der Geraden \(BE\) alle spiegelsymmetrisch zu \(g_3\), der Mittelsenkrechten zu \(BE\). Sein nun \(G_4\) der Graph, den wir erhalten, wenn wir alle Knoten die in \(G_1\) zwischen \(BE\) und \(g_2\) liegen an \(g_3\) spiegeln, wodurch \(g_1\) und \(g_2\) parallel werden (Abb. 8). \(G_5\) sei der Graph, den wir erhalten, wenn wir \(G_4\) an \(BE\) spiegeln.

Die beiden neuen Teilgraphen \(G_4\) und \(G_5\) können wir jetzt als eine Art Adapter benutzen, um mit \(G_1\) konstruierte Kreiselemente in wechselnder Richtung aneinanderzusetzen. Dadurch werden unendlich viele andere Formen neben Ringen möglich (Abb. 9). Das kann man sich ungefähr so vorstellen, als wenn man eine ebene geschlossene Strecke für eine Modelleisenbahn auslegt und nur Links- und Rechtskurven als Schienenelemente zur Verfügung hat.

[1] Heiko Harborth, Plane four-regular graphs with vertex-to-vertex unit triangles, Discrete Mathematics 97 (1991), 219-222. (PDF) [2] Mike Winkler, Peter Dinkelacker, Stefan Vogel, 4-Regular Planar Unit Triangle Graphs without Additional Triangles, Geombinatorics Quarterly, Volume XXIX, Issue 2, October 2019, pp. 72-77. (PDF) [3] Stefan Vogel, Matchstick Graphs Calculator (MGC), a software for the construction and calculation of unit distance graphs and matchstick graphs, (2016–2019). (MGC) • Dies ist ein weiterer Artikel in dem Lösungen zu offenen Problemen aus der Graphentheorie präsentiert werden, die sich aus der gemeinsamen Arbeit von haribo, StefanVogel und mir in unserem Streichholzgraphen-Thread ergeben haben. Dieser Artikel orientiert sich am Original in englischer Sprache, welches im Oktober 2019 bei Geombinatorics Quarterly erschienen ist. Die original Version ist als PDF verfügbar [2]. • haribo ist der eigentliche Star dieses Artikels, denn er war es, der die entscheidende Idee zur Konstruktion solcher Graphen hatte (hier). Wie man im Thread nachlesen kann, hatte ich schon nicht mehr an eine Lösung geglaubt. Die Ideen zu den Teilgraphen in den Abbildungen 4, 7 und 8, wie auch die Idee zur Konstruktion der Nicht-Ringe mit dem Harborth-Teilgraphen, stammen alle von haribo. StefanVogel war wie immer durch seine Berechnungen der Graphen beteiligt und ganz besonders am Finden der kleinsten Lösung. Die tolle Beweis-Idee mit den Schienen stammt auch von ihm. Wer es ganz genau wissen will, der kann unseren Thread durchgehen, der ja eine Chronologie unserer Arbeit darstellt. • Fairer Weise muss man darauf hinweisen, dass die minimale Lösung so geringe Abstände zwischen Knoten und Kanten besitzt (vgl. Abb. 5), dass eine Konstruktion aus kleinen Papp-Dreiecken kaum umzusetzen wäre. Die große Anzahl der Dreiecke ist natürlich eine weitere Hürde für den Hobby-Bastler. • Der erste Graph mit den in der Aufgabenstellung geforderten Eigenschaften wurde am 19.09.2018 konstruiert (hier). Er besteht aus 63072 Dreiecken und hat die Symmetrie eines regelmäßigen 292-Ecks. Ein wahres Monstrum. Seine Größe wurde allerdings willkürlich gewählt, da es hier erstmal nur um einen Existenzbeweis ging. • Ich bedanke mich bei unserem ehemaligen Mitglied cis für seine Unterstützung bei der Umsetzung der Grafiken mit TikZ/PGFplots. (siehe auch hier) Die Bilder in diesem Artikel sind allerdings PNG's dieser Grafiken. • Und - last but definitely not least - bedanke ich mich bei haribo und StefanVogel für die angenehme Zusammenarbeit im Thread, die hoffentlich noch viele Früchte tragen wird. Viele Grüße, Slash