A theorem on graphs. (Q574248)

Verf. betrachtet zusammenhängende Graphen, die sich so auf die Kugelfläche legen lassen, daß jedes der durch den Graphen bestimmten Gebiete der Kugel ein Dreieck ist, abgesehen von diesen Elementardreiecken aber in dem Graphen keine aus einer, zwei oder drei Kanten aufgebauten Kreise existieren. In einem solchen Graphen gibt es -- so lautet das Hauptergebnis (Satz I) -- einen Kreis, der durch alle Knotenpunkte hindurchgeht. Die Forderung, daß außer den Elementardreiecken keine aus drei Kanten bestehenden Kreise auftreten, ist, wie ein Beispiel zeigt, wesentlich. Der Satz ergibt sich aus dem folgenden Lemma, wenn man darin für \(R\) ein Elementardreieck, für das Innere von \(R\) die Komplementärmenge der Dreiecksfläche auf der Kugel nimmt. Lemma: Wenn in dem Graphen ein Kreis \(R\) existiert, der sich durch zwei oder drei Knotenpunkte \(A, B\) bzw. \(A, B, C\) so in zwei bzw. drei Teile \(R_i\) (\(i = 1,2\) bzw. \(1, 2, 3\)) zerlegen läßt, daß es in einem der beiden durch \(R\) bestimmten Gebiete der Kugel -- es heiße das Innere von \(R\) -- keine Kante des Graphen gibt, die zwei Knotenpunkte einunddesselben \(R_1\) (einschließlich der Endpunkte) miteinander verbindet, so kann man in dem Graphen \(A\) und \(B\) durch einen auf und innerhalb von \(R\) verlaufenden Kantenzug verbinden, der jeden auf oder innerhalb von \(R\) gelegenen Knotenpunkt genau einmal trifft. Der Beweis verläuft induktiv, nach der Anzahl der auf und innerhalb von \(R\) gelegenen Knotenpunkte, und ist elementar, erfordert aber eine Reihe von Fallunterscheidungen. -- Deformiert man den Graphen so, daß der nach Satz I existierende Kreis durch alle Knotenpunkte ein reguläres Polygon wird, so erhält man eine besonders übersichtliche Figur, die Verf. als Normalform des Graphen bezeichnet. Die Anzahl der Möglichkeiten, ein reguläres \(n\)-Eck durch Diagonalen in Dreiecke zu zerlegen, ist durch \textit{Euler} und \textit{Lamé} bekannt ; doch liefern nicht alle solche Teilungen des Innen- und Außengebiets Normalformen von Graphen, und viele liefern denselben Graphen. Durch Übergang zu der zu dem Graphen dualen Zerlegung der Ebene in Gebiete erhält man einen analogen Satz über die Möglichkeit, die Länder einer Karte -- jedes genau einmal -- auf einem geschlossenen Weg zu durchlaufen; von den Ländern muß dabei gefordert werden, daß jedes Land sowie jeder aus zwei oder drei Ländern bestehende Bereich, falls er zusammenhängend ist, einfach zusammenhängend ist, außerdem, daß in jeder Ecke genau drei Länder zusammenstoßen. Es handelt sich dabei übrigens um einen Typ von Karten, auf den man das allgemeine Vierfarbenproblem zurückführen kann.