Congruent graphs and the connectivity of graphs (Q567002)

Verf. betrachtet zunächst Graphen, in denen keine Schlingen auftreten und keine zwei Knotenpunkte durch mehr als eine Kante verbunden sind. Wenn zwischen den Kannten zweier solcher Graphen eine eineindeutige Zuordnung besteht, bei der zwei Kanten des einen Graphen dann und nur dann einen Knotenpunkt gemeinsam haben, wenn dasselbe für die entsprechenden Kanten des anderen gilt, so zeigt ein triviales Beispiel, daß\ zwei solche Graphen nicht notwendig kongruent, d. h. ihre Ecken und Kanten eineindeutig unter Erhaltung der Inzidenzbeziehnung aufeinander bezogen sind: Der aus drei Kanten mit genau einem gemeinsamen Knotenpunkt bestehende Graph ist dem aus den Ecken und Seiten eines Dreiecks bestehenden Graphen nicht kongruent. Das ist aber - so zeigt Verf. - der einzige Ausnahmefall: Wenn keiner der beiden Graphen der aus drei Kanten mit einer gemeinsamen Ecke bestehende Graph ist, so folgt aus dem Bestehen einer Kantenzuordung von der oben erwähnten Art die Kongruenz der beiden Graphen. Weitere Aussagen ähnlicher Art kann man für dreifach zusammenhängende Graphen machen. Ein zusammenhängender Graph mit wenigstens \(n+1\) Knotenpunkten heißt \(n\)-fach zusammenhängend, wenn es nicht möglich ist, aus ihm \(n-1\) oder weniger Knotenpunkte samt den in ihnen endenden Kanten wegzulassen, derart daß\^^Mder entstehende Graph nicht mehr zusammenhängend ist, ein Graph, der \(n\)-fach, aber nicht \((n+1)\)-fach zusammenhängend ist, hat die Zusammenhangszahl (``connectivity'') \(n\). Es wird bewiesen: Wenn zwischen den Kanten zweier dreifach zusammenhängender Graphen eine eineindeutige Zuordnung besteht, bei der Kreise oder auch Teilgraphen der Nullität 1 einander entsprechen, so sind die beiden Graphen einander kongruent. Über die Struktur der \(n\)-fach zusammenhängenden Graphen (in denen jetzt zwei Ecken auch durch mehrere Kanten verbunden sein dürfen) werden folgende Aussagen gemacht: Dann und nur dann ist ein Graph \(n\)-fach zusammenhängend, wenn mann ihn für kein \(k<n\) aus zwei mehr als \(k\) Knotenpunkte enthaltenden Graphen durch Identifikation von \(k\) Knotenpunkten aufbauen kann. Ein Graph mit mindestens zwei Knotenpunkten, der durch Tilgen von weniger als \(n\) Kanten zerlegt werden kann, ist nicht \(n\)-fach zusammenhängend. Läßt man aus einem \(n\)-fach zusammenhängenden Graphen einen Knotenpunkt und die in ihm endenden Kanten weg, so entsteht ein \((n-1)\)-fach zusammenhängender Graph. Dann und nur dann ist ein Graph, in dem zwei Knotenpunkte durch höchstens eine Kante verbunden sind, \(n\)-fach zusammenhängend, wenn je zwei Knotenpunkte durch \(n\) bis auf die gemeinsamen Endpunkte paarweise (kanten- und knotenpunkt- )fremde Kantenzüge verbunden werden können (vgl. hierzu \textit{Menger}, Fundamenta 10 (1926), 96-115; F. d. M. 53, 561 (JFM 53.0561.*); \textit{N. Rutt}, 1929; F. d. M. \(55_{\text{I}}\), 330; ferner \textit{D. König}, 1933; F. d. M. \(59_{\text{II}}\), 1232). Bei der Untersuchung dualer Graphen (siehe vorstehendes Referat) läßt man zweckmäßigerweise auch Graphen mit Schlingen und mehreren Verbindungen desselben Knotenpunktpaares zu. Zwischen den Zusammenhangseigenschaften zweier zusammenhängender zueinander dualer Graphen besteht folgende Beziehung: \(G\) sei nicht-separabel und zerfalle, wenn man die Ecken \(a_1, a_2, \dots, a_n\) mit den in ihnen endenden Kanten tilgt, in zwei Bestandteile \(H_1\) und \(H_2\), während keine echte Teilmenge der \(a_i\) mit den zugehörigen Kanten \(G\) zerlegt. Die Nullität von \(H_1\) sei positiv, oder wenigstens ein \(a_i\) sei mit \(H_1\) durch wenigstens zwei Kanten verbunden; entsprechend für \(H_2\). Wenn dann \(G'\) zu \(G\) dual ist, so kann \(G'\) durch Tilgen einer den \(a_i\) in bestimmter Weise zugeordneten Menge von \(n\) Kanten zerlegt werden. Für dreifach zusammenhängende Graphen ohne Schlingen und ohne mehrfache Verbindungen von Knotenpunktpaaren liefert dieser Satz: Jeder dazu duale Graph ist ebenfalls dreifach zusammenhängend, und - in Verbindung mit einem der obigen Kongruenzsätze -: Der duale Graph ist in diesem Fall eindeutig bestimmt.