Non-separable and planar graphs. (English) JFM 58.0608.01

Whitney, H.

Transactions A. M. S. 34, 339-362 (1932).

Diese Arbeit bildet die Grundlage einer Reihe weiterer Arbeiten des Verf. zur kombinatorischen Theorie der Graphen. Sie enthält in ihrem ersten Teil eine Untersuchung des Aufbaus von Graphen aus gewissen “nicht-separablen” Bestandteilen, wie sie sich ähnlich auch bei D. König (1933; F. d. M. \(59_{\text{II}}\), 1232, insbes. §1 dieser Arbeit) findet. Der zweite Teil bringt eine interessante kombinatorische Charakterisierung derjenigen Graphen, die sich in die Ebene (oder die Kugelfläche) einbetten lassen (“planare” Graphen); inzwischen ist es Verf. gelungen, daraus die Kuratowskische Kennzeichnung der nicht-planaren Graphen auf kombinatorischem Wege abzuleiten (Kuratowski, 1930; F. d. M. \(56_{\text{II}}\), 1141; Verf., Fundamenta 21 (1933), 73-84; F. d. M. \(59_{\text{II}}\), 1235).
Ein zusammenhängender Graph heißt nicht-separabel, wenn man ihn nicht aus zwei Graphen, deren jeder wenigstens eine Kante enthält, durch Verschmelzung eines Paares von Knotenpunkten entstanden denken kann; andernfalls heißt ein Graph (insbesondere auch jeder nicht-zusammenhängende Graph) separabel. Separabel ist z. B. jeder aus mehr als einer Kante bestehende Baum, nicht separabel ein Kreis (= einfach geschlossenes Polygon, “circuit”). Man erhält eine eindeutig bestimmte Zerlegung eines Graphen in nicht-separable Bestandteile - “Komponenten” (bei König: Glieder) -, wenn man jeden zusammenhängenden Bestandteil des Graphen in jedem etwa vorhandenen trennenden Knotenpunkt der oben angegebenen Art (“cut vertex”, bei König und Sainte Laguë: Artikulation) aufschneidet, wobei der trennende Knotenpunkt selbst in jeder der Komponenten, denen er angehört, durch einen Knotenpunkt repräsentiert wird. Jeder nicht-separable Teilgraph ist ganz in einer Komponente enthalten. Ein zusammenhängender separabler Graph ist aus seinen Komponenten nach Art einer Baumkurve aufgebaut, derart, daßje zwei Komponenten höchstens einen Knotenpunkt gemeinsam haben uns es keinen Zyklus von Komponenten gibt, in dem je zwei benachbarte Komponenten einen Punkt gemeinsam haben. Versteht man unter dem Rang \(R\) eines Graphen die Zahl \(V-P\), \(V\)=Anzahl der Knotenpunkte, \(P\)=Anzahl der zusammenhängenden Bestandteile, unter der Nullität ( = erste Bettische Zahl) die Zahl \(E-R\), \(E=\)Anzahl der Kanten, so sind Rang und Nullität eines Graphen gleich der Summe der Ränge bzw. Nullitäten seiner Komponenten.
Die nicht-separablen Graphen sind dadurch gekennzeichnet, daßje zwei ihrer Ecken in einem Kreis enthalten sind (“zyklisch zusammenhängende” Graphen); es ist also \(N>0\). \(P=1, N=1\) kennzeichnet die Kreise. Als Gegenstück der Ranggleichung für separable Graphen hat man folgende Kennzeichnung der nicht-separablen: Verteilt man die Kanten des Graphen irgendwie auf zwei Teilgraphen, von denen jeder mindestens eine Kante enthalten soll, so gilt für die Ränge \(R\), \(R_1\), \(R_2\) der drei Graphen \(R<R_1+R_2\). Setzt man endlich viele nicht-separable Graphen durch Verschmelzen je eines Paares von Knotenpunkten zyklisch zusammen (wobei natürlich in jedem einzelnen Graphen zwei verschiedene Knotenpunkte mit denen der beiden Nachbarn zu identifizieren sind), so entsteht wieder ein nicht-separabler Graph. Jeder nicht separable Graph, der wenigstens zwei Kanten enthält, kann, ausgehend von einem Kreis, Schritt für Schritt in der Weise aufgebaut werden, daßman die Endpunkte einer neuen Kante oder eines neuen einfachen Kantenzuges mit zwei verschiedenen Knotenpunkten des schon vorhandenen Teiles identifiziert.
Zwei Graphen heißen kongruent (in früheren Arbeiten des Verf: homöomorph), wenn sich ihre Kanten und Knotenpunkte unter Erhaltung der Inzidenzen eineindeutig aufeinander beziehen lassen; sie heißen äquivalent, wenn ihre Komponenten paarweise kongruent sind, abgesehen von vielleicht auftretenden isolierten Knotenpunkten. Ein Graph \(G'\) heißt zu einem Graphen \(G\) dual, wenn eine eineindeutige Zuordnung zwischen den Kanten von \(G\) und von \(G'\) besteht, die folgende Eigenschaft hat: Ist \(H\) ein Teilgraph von \(G\), \(H'\) derjenige Teilgraph von \(G'\), der aus allen und nur den Kanten von \(G'\) besteht, die nicht Bilder der Kanten von \(H\) sind, so gilt stets \(R(H')=R(G')-N(H)\) (\(R\)=Rang, \(N\)=Nullität). Dann ist auch \(G\) zu \(G'\) dual, und es gilt \(R(G')=N(G)\), \(R(G)=N(G')\). Die Dualitätsbeziehung zwischen zwei Graphen wird weitgehend durch die zwischen den Komponenten bestimmt: Ist \(G'\) zu \(G''\) äquivalent, \(G'\) zu \(G\) dual, so ist auch \(G''\) zu \(G\) dual (aber ein Graph kann untereinander nicht äquivalente Duale haben). Sind die Komponenten von \(G\) und \(G'\) paarweise zueinander dual, so auch \(G\) und \(G'\). Sind die Kanten zweier Graphen \(G\) und \(G'\) eineindeutig so aufeinander bezogen, daßdie Abbildung zugleich eine Abbildung zwischen den Paaren von Komponenten von \(G\) und \(G'\) ist, so sind \(G\) und \(G'\) dual. Umgekehrt: Bei der die Dualität vermittelnden Abbildung der Kanten entsprechen den Komponenten von \(G\) die Komponenten von \(G'\). Insbesondere ist ein zu einem nicht-separablen Graphen dualer Graph nicht-separabel.
Nicht jeder Graph besitzt einen Dualen. Es gilt vielmehr der Satz: Dann und nur Dann besitzt ein Graph einen Dualen, wenn er planar ist. Zum Beweis kann man sich offenbar auf nicht-separable Graphen beschränken, da sowohl die Möglichkeit der Einbettung in die Ebene als auch die Dualität nur von den einzelnen Komponenten abhängt. Zunächst zeigt sich, daßbeim Übergang von der durch einen Graphen bewirkten Zerlegung der Kugel zu der im üblichen Sinn der Mannigfaltigkeitstheorie dualen Zerlegung in der Tat ein im kombinatorischen Sinn dualer Graph entsteht. Umgekehrt zeigt ein Induktionsschluß, bei dem der schrittweise Aufbau der nicht-separablen Graphen benutzt wird, daßzwei im kombinatorischen Sinn duale Graphen sich so auf die Kugel legen lassen, daßsie zwei zueinander im üblichen Sinn duale Einteilungen der Kugel liefern. Aus der Existenz eines kombinatorisch Dualen zu einem planaren Graphen und der kombinatorischen Dualitätsbedingung folgt natürlich die Eulersche Polyederformel. Als ersten Schritt in Richtung auf das Kuratowskische Ergebnis zeigt Verf. noch: Keiner der beiden Kuratowskischen nicht-planaren Graphen besitzt einen Dualen.

Reviewer: Pannwitz, Erika, Dr. (Berlin)

JFM Section:

Erster Halbband. Fünfter Abschnitt. Geometrie. Kapitel 2. Topologie.