Planar graphs. (Q559382)

In einer früheren Arbeit (Non-separable and planar graphs, Transactions A. M. S. 34 (1932), 339-362; F. d. M. 58) hat Verf. bewiesen: Dann und nur dann ist ein Graph planar (d. h. kann er in die Ebene eingebettet werden), wenn dazu ein dualer Graph existiert. Hieraus leitet Verf. das \textit{Kuratowski}sche Kriterium für die Möglichkeit der Einbettung in die Ebene ab (\textit{Kuratowski}, 1930; F. d. M. \(56_{\text{II}}\), 1141-1142), indem er zeigt: Dann und nur dann besitzt ein Graph \(G\) einen dualen \(G'\), wenn \(G\) keinen der beiden folgenden Graphen \(K_1\) und \(K_2\) als Teilgraphen enthält: \(K_1\) besteht aus fünf Punkten, von denen jeder mit jedem anderen durch eine Kante oder einen einfachen Kantenzug verbunden ist, wobei verschiedene Kantenzüge bis auf die Endpunkte zueinander fremd sind; \(K_2\) erhält man, indem man zweimal drei Knotenpunkte nimmt und jeden Punkt des einen Tripels mit jedem Punkt des anderen durch eine Kante oder einen einfachen Kantenzug, mit derselben Bedingung wie oben, verbindet. Der Beweis ist bemerkenswert, weil er im wesentlichen kombinatorisch ist und geometrische Betrachtungen auf das für einen Einbettungssatz unbedingt Notwendige beschränkt sind. Die Notwendigkeit der Bedingung hat Verf. schon früher (a. a. O.) bewiesen. Daß\ die Bedingung auch hinreicht, wird durch einen Induktionsschluß\ nach der Kantenzahl bewiesen, wobei man sich auf nichtseparable Graphen beschränken kann und von der Möglichkeit, einen nichtseparablen Graphen schrittweise aus nichtseparablen aufzubauen (a. a. O.), Gebrauch macht. Insbesondere dient dazu ein Satz (Satz 11), der das Verhalten des Dualen bei gewissen einfachen Abänderungen des Graphen beschreibt. In der Untersucheungen, die dem Beweis des Hauptsatzes vorangehen, ist Verf. über das für den Beweis Erforderliche hinausgegangen und zu folgenden Ergebnissen gelangt: Wenn zwischen den Kanten zweier Graphen \(G\) und \(G'\) eine eineindeutige Zuordnung besteht derart, daß\ Kreise einander entsprechen, so sind entsprechende Teilgraphen von \(G\) und \(G'\) von gleichem Rang und gleicher Nullität. \(G\) und \(G'\) sind dann 2-isomorph (vgl. das vorletzte Referat). Dabei kann man Kreise durch Graphen ersetzen, deren zusammenhängende Bestandteile Bäume sind (``forest''), oder durch Teilgraphen von der Nullität 1, Teilgraphen von positiver Nullität, trennende Kantenmengen (vgl. das vorangehende Referat), Teilgraphen ohne trennende Kantenmenge, Teilgraphen mit wenigstens einer oder solche mit genau einer trennenden Kantenmenge. Ist die Zuordnung zwischen den Kanten so, daß\ Kreise von \(G\) und trennende Kantenmengen von \(G'\) einender entsprechen, oder auch Teilgraphen von \(G\) ohne trennende Kantenmenge und forests von \(G'\), oder Teilgraphen von \(G\) mit wenigstens einer trennenden Kantenmenge und Teilgraphen posotiver Nullität von \(G'\), oder Teilgraphen von \(G\) mit genau einer trennenden Kantenmenge und Teilgraphen der Nullität 1 von \(G'\), so sind \(G\) und \(G'\) zueinander dual, woraus folgt: Ist \(G\) zu \(G'\) dual, so ist \(G''\) zu \(G\) dann und nur dann dual, wenn \(G'\) zu \(G''\) 2-isomorph ist. Trennende Kantenmengen und Kreise entsprechen in dualen Graphen eineander gegenseitig. Für die Trennenden Kantenmengen gelten folgende Sätze: Nimmt man aus einem Graphen eine trennende Kantenmenge heraus, so enthält der entstehende Graph zwei zusammenhängende Bestandteile derart, daß\ jede Kante der trennenden Kantenmenge diese beiden Bestandteile verbindet. Je zwei Kanten der trennenden Kantenmenge sind in einem Kreis enthalten, und jeder Kreis hat mit der trennenden Kantenmenge eine gerade Anzahl von Kanten gemainsam. Jede trennende Kantenmenge liegt ganz in einer Komponente (maximalem nichtseparablen Bestandteil) des Graphen. - Mit den verschiedenen Möglichkeiten der Einbettung des Graphen in die Ebene und den entsprechenden Zerlegungseigenschaften der Kreise scheint die folgende Begriffsbildung in Zusammenhang zu stehen: \(G\) sei nichtseparabel, \(G'\) zu \(G\) dual, und \(P\) ein Kreis von \(G\), \(P'\) die ihm entsprechende trennende Kantenmenge in \(G'\). Den beiden Komponenten von \(G'\) - \(P'\) entsprechen dann zwei Teilgraphen von \(G\), die als die veiden ``Seiten von \(P\) in \(G\) in bezug auf den dualen Graphen \(G'\)'' bezeichnet werden. Zwei Knotenpunkte von \(G\), die durch einen zu \(P\) fremden Kantenzug verbunden werden können, liegen immer auf derselben Seite von \(P\) (aber natürlich nicht umgekehrt).