Zum Satz von Hajnal und Surányi

Bearbeiten

Es gilt der folgende Lehrsatz, der auf eine Arbeit von András Hajnal und János Surányi aus dem Jahre 1958 zurückgeht: [1][1]

Ist   ein endlicher, schlichter, chordaler Graph und , so stimmen für jeden induzierten Teilgraphen   von   die Unabhängigkeitszahl   überein mit der kleinsten Anzahl   von Cliquen einer Cliquenüberdeckung von  .

Literatur

Bearbeiten

Satz von Mantel

Bearbeiten

Der Satz von Mantel , englisch Mantel's theorem, ist einer der klassischen Lehrsätze des mathematischen Teilgebiets der extremalen Graphentheorie. Der Satz geht auf eine Arbeit von W. Mantel aus dem Jahre 1907 zurück und behandelt eine Bedingung, unter der ein Graph Dreiecke enthält.[2][3][A 1]

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich zusammengefasst angeben wie folgt:[2]

Gegeben sei ein endlicher schlichter Graph   der Knotenzahl   und der Kantenzahl  .
Dabei soll die Ungleichung
 
erfüllt sein.
Dann enthält   einen Kreisgraphen vom Typ  .
Anders gesagt:
Ist ein endlicher schlichter Graph der Knotenzahl   dreiecksfrei, so besitzt er höchstens   Kanten.[A 2]

Verwandter Satz

Bearbeiten

Von István Reiman (1927–2012) wurde im Jahre 1958 ein dem Mantel'schen verwandter Satz vorgelegt, welcher die entsprechende Fragestellung für den Kreisgraphen vom Typ   behandelt. Dieser Satz lässt sich angeben wie folgt:[4][5]

Sei   ein endlicher schlichter Graph der Knotenzahl   und der Kantenzahl   und sei weiter vorausgesetzt, dass   keinen Kreisgraphen des Typs   enthalte.
Dann ist die Ungleichung
 [A 3]
erfüllt.

Hintergrund

Bearbeiten

Zum Beweis des Mantel’schen Satzes werden in der Monographie Extremal Combinatorics von Stasys Jukna sowohl die Cauchy-Schwarzsche Ungleichung als auch (nicht zuletzt) zwei elementare Formeln zu Mengensystemen auf endlichen Mengen herangezogen.[A 4] Letztere lassen sich angeben wie folgt:[6]

Gegeben sei eine endliche Menge   sowie ein Teilmengensystem   und dazu der Hypergraph  .
Dabei sei   die zugehörige  -Gradfunktion.
Dann gelten folgende Formeln:
(i)   .[A 5]
(ii)   .

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten

rreferences />

Anmerkungen

Bearbeiten

rreferences group="A" />

KKKategorie:Satz (Graphentheorie)|Mantel]]

Satz von Ghouila-Houri

Bearbeiten

In der Theorie der gerichteten Graphen, einem der Teilgebiete der Graphentheorie, ist der Satz von Ghouila-Houri das Pendant zum Satz von Dirac in der Theorie der ungerichteten Graphen. Der Satz geht auf eine Arbeit des französischen Mathematikers Alain Ghouila-Houri aus dem Jahre 1960 zurück. Von mehreren Autoren wird hervorgehoben, dass der Beweis des Ghouila-Houri'schen Satzes um einiges schwieriger sei als der des diracschen.[7][8][9]

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich zusammengefasst angeben wie folgt:

Gegeben sei ein endlicher gerichteter Graph  .
  sei stark zusammenhängend und habe zudem die Eigenschaft, dass an jedem Knoten   für den Grad   in Bezug auf die Knotenzahl   durchweg die Ungleichung
 
erfüllt ist.
Dann besitzt   einen hamiltonschen Zyklus, also einen Zyklus, auf dem alle Knoten von   genau einmal vorkommen.
Insbesondere gilt diese Aussage für den Fall, dass an jedem Knoten   hinsichtlich Eingangsgrad und Ausgangsgrad die beiden Ungleichungen
 
und
 
erfüllt sind.

Verschärfung

Bearbeiten

Der Satz von Ghouila-Houri wurde von mehreren Autoren verschärft; so im Jahre 1973 von M. Meyniel wie folgt:[10]

Ist   ein endlicher stark zusammenhängender gerichteter Graph, der für je zwei verschiedene nicht benachbarte Knoten   und   die Ungleichung
 .
erfüllt, so besitzt   einen hamiltonschen Zyklus.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten

rreferences />

KKKategorie:Satz (Graphentheorie)|Ghouila-Houri]] KKKategorie:Satz (Mathematik)|Ghouila-Houri]]

Satz von Berge

Bearbeiten

In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Berge einer von mehreren Sätzen, die auf den französischen Mathematiker Claude Berge (1926–2002) zurückgehen. Berge publizierte den Satz im Jahre 1957 und gab damit eine Charakterisierung größtmöglicher Matchings in endlichen Graphen. In dieser Publikation gab Berge auch einen Algorithmus zur Bestimmung eines solchen Matchings.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[11][12][13][14]

Ein Matching   in einem endlichen Graphen   ist von maximaler Mächtigkeit (und besteht damit aus genau   Kanten) dann und nur dann, wenn es in   keinen  -erweiternden Weg gibt.

Erklärungen

Bearbeiten
  • In einem endlichen Graphen   ist ein Matching   von maximaler Mächtigkeit genau dann, wenn in   kein anderes Matching   existiert mit  . Die Mächtigkeit eines solchen größtmöglichen Matchings nennt man die Matchingzahl von   und bezeichnet sie mit  .
  • Ist ein Weg in   gegeben, so wird   als  -alternierend bezeichnet, falls die in   vorkommenden Kanten abwechselnd zu   und zu   gehören.
  • Inzidieren die durch einen  -alternierenden Weg   verbundenen Endknoten mit keiner der in   vorkommenden Kanten, so wird   als  -erweiternd (oder als  -zunehmend) bezeichnet.

Anmerkungen

Bearbeiten
  • In der englischsprachigen Graphentheorieliteratur spricht man von einem augmenting path. Daher ist der Satz von Berge hier auch als augmenting path theorem bekannt.[15][16]
  • Der Satz tritt auch schon in der Pionierarbeit Die Theorie der regulären Graphs des dänischen Mathematikers Julius Petersen aus dem Jahre 1891 auf.[16]
  • Oft wird (so etwa im Bronstein) ein Matching von maximaler Mächtigkeit auch kurz ein maximales Matching genannt, obwohl diese Benennung nicht dem sonst üblichen – von der Ordnungstheorie herrührenden – Maximalitätsbegriff entspricht.[14]

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Berge]] KKKategorie:Satz (Mathematik)|Berge]]



Satz von Babai

Bearbeiten

Der Satz von Babai ist ein mathematischer Lehrsatz, welcher im Übergangsfeld zwischen den Teilgebieten Graphentheorie und Gruppentheorie angesiedelt ist. Er geht auf eine Veröffentlichung des ungarischen Mathematikers László Babai aus dem Jahre 1974 zurück. Der Satz ist verwandt mit dem Satz von Frucht, denn er behandelt eine spezielle Problemstellung im Zusammenhang mit der Frage der Darstellbarkeit endlicher Gruppen als Automorphismengruppen schlichter Graphen. Er zieht als Folgerung nach sich, dass eine von Pál Turán im Jahre 1969 gestellte Frage, ob nämlich jede endliche Gruppe als Automorphismengruppe eines ebenen Graphen darstellbar ist, verneinend zu beantworten ist. [17]

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[18]

Sei   eine Klasse schlichter Graphen mit den folgenden beiden Eigenschaften:
(1)   enthält mit einem schlichten Graphen   stets auch jedes graphenhomomorphe Bild eines jeden Minors   .
(2) Zu jeder endlichen Gruppe   gebe es in   einen (möglicherweise unendlichen) schlichten Graphen  , dessen Automorphismengruppe   gruppenisomorph zu   ist.
Dann gilt:
Die Graphenklasse   enthält alle endlichen schlichten Graphen.

Quellen und Literatur

Bearbeiten

Siehe auch

Bearbeiten

Einzelnachweise

Bearbeiten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Gruppentheorie]] KKKategorie:Satz (Graphentheorie)]] KKKategorie:Satz (Mathematik)]]

Satz von Tutte (Hamiltonkreisproblem)

Bearbeiten

In der Topologischen Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Tutte zum Hamiltonkreisproblem einer der Lehrsätze des britisch-kanadischen Graphentheoretikers William Thomas Tutte (1917–2002). Tutte publizierte den Satz im Jahre 1956 und verknüpft dabei – an ein Resultat von Hassler Whitney aus dem Jahre 1931 anschließend – das Hamiltonkreisproblem mit der Frage der Plättbarkeit und des mehrfachen Zusammenhangs. Der Satz ist bedeutsam in Bezug auf das Vier-Farben-Problem.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[19]

Ist ein endlicher schlichter Graph   plättbar und  -fach zusammenhängend, so enthält   einen hamiltonschen Kreis.

Der Satz lässt sich auch so formulieren:[20]

In jedem endlichen schlichten Graphen  , der plättbar ist und keinen minimalen Schnitt mit drei oder weniger Knoten enthält, gibt es einen hamiltonschen Kreis.

Der whitneysche Satz

Bearbeiten

Der von Hassler Whitney 1931 vorgelegte Satz macht die gleiche Aussage wie der tuttesche Satz, tut dies allerdings unter einer zusätzlichen Voraussetzung. Es soll nämlich hier der den Graphen darstellenden Streckengraph zusätzlich der Bedingung genügen, dass jedes Land seiner topologischen Landkarte eine Dreiecksfläche in der euklidischen Ebene ist.[19]

Bezug zum Vier-Farben-Problem

Bearbeiten

Wie Hansjoachim Walther/Heinz-Jürgen Voß[19] und Øystein Ore[21] ausführen, ist für die topologischen Landkarten der betrachteten Graphen das Vier-Farben-Problem gelöst. Denn ein solcher Graph lässt sich stets derart in die Oberfläche der Einheitskugel einbetten, dass die Knoten des hamiltonschen Kreises sämtlich auf dem Äquators der Kugeloberfläche zu liegen kommen. Davon ausgehend lässt sich durch vollständige Induktion nachweisen, dass sowohl die Länder der Nordhalbkugel der zugehörigen topologischen Landkarte als auch ihre Länder auf der Südhalbkugel stets eine zulässige Färbung mit zwei Farben besitzen, weswegen die gesamte topologische Landkarte eine zulässige Färbung mit vier Farben gestattet.[22]

Quellen und Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Graphentheorie)]] KKKategorie:Satz (Mathematik)]]

Satz von Battle-Harary-Kodama

Bearbeiten

Der Satz von Battle-Harary-Kodama ist ein mathematischer Lehrsatz, welcher dem Gebiet der Topologischen Graphentheorie angehört und auf eine Veröffentlichung der drei Mathematiker Joseph Battle, Frank Harary und Yukihiro Kodama aus dem Jahre 1962 zurückgeht. Er behandelt die Frage der Plättbarkeit von endlichen schlichten Graphen und der zugehörigen Komplementärgraphen und beruht auf einer Vermutung von John L. Selfridge. Im Jahre 1963 hat William Tutte einen vereinfachten Beweis des Satzes geliefert.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[23]

(1) Ist ein endlicher schlichter Graph   plättbar und hat er   Knoten, so ist sein Komplementärgraph   nicht plättbar.
(2) Die Zahl   ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Verwandter Satz

Bearbeiten

Von D. P. Geller wurde ein verwandter Satz vorgelegt,[24] welcher die analoge Frage in Bezug auf die Eigenschaft der kreisartigen Plättkeit behandelt. Hier bezeichnet man einen endlichen schlichten Graphen   als kreisartig plättbar, wenn   eine ebene Darstellung in Form eines Streckengraphen   besitzt, dessen Knoten sämtlich Randpunkte eines einzigen Landes der zugehörigen topologischen Landkarte sind.[25][26]

Der Satz von Geller lässt sich dann so formulieren:[24]

(1) Ist ein endlicher schlichter Graph   kreisartig plättbar und hat er   Knoten, so ist sein Komplementärgraph   nicht kreisartig plättbar.
(2) Die Zahl   ist die kleinste natürliche Zahl mit dieser Eigenschaft.

Quellen und Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Battle-Harary-Kodama, Satz von]] KKKategorie:Satz (Mathematik)|Battle-Harary-Kodama, Satz von]]


Satz von Steinitz

Bearbeiten

Der Satz von Steinitz, englisch Steinitz's theorem, ist ein mathematischer Lehrsatz, welcher sowohl dem Gebiet der Topologischen Graphentheorie als auch dem der Geometrischen Graphentheorie zuzurechnen ist. Der Satz geht zurück auf eine Veröffentlichung des Mathematikers Ernst Steinitz (1871–1928) aus dem Jahre 1916 und zählt zusammen mit dem eulerschen Polyedersatz, dem Satz von Kuratowski und dem Satz von Wagner zu den klassischen Ergebnissen der Graphentheorie über plättbare Graphen.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[27][28][29]

Ein endlicher schlichter Graph   hat dann und nur dann eine geradlinige Darstellung als  -dimensionaler Polyedergraph  , wenn   plättbar und zugleich  -fach zusammenhängend ist.

Bedeutung des Satzes

Bearbeiten

Der steinitzsche Satz ist einer der grundlegenden Sätze in der Lehre von den Polyedern und offenbar schätzte auch Ernst Steinitz dies selbst so ein. Wie Branko Grünbaum hierzu in seinem 1975er Artikel Polytopal Graphs hervorhebt, bezeichnete Steinitz seinen Satz daher sogar als Fundamentalsatz der konvexen Typen [von Polyedern] (englisch Fundamental Theorem of Convex Types [of Polyhedra]) und präsentierte dazu nicht weniger als drei sorgfältig ausgearbeitet Beweise. Diese sind in der klassischen Monographie Vorlesungen über die Theorie der Polyeder von Steinitz und Rademacher dargestellt. Wie Grünbaum weiter schreibt, bedient sich diese Darstellung jedoch nicht der modernen Begriffe der Graphentheorie - wie den des Zusammenhangs oder den der Plättbarkeit - sondern eigener Begrifflichkeiten, wodurch Steinitz' Beweisführung (aus heutiger Sicht) recht schwerfällig (englisch rather cumbersome) sei.[30]

Verwandter Satz

Bearbeiten

Ein verwandter Satz, welcher die Polytope aller höheren Dimensionen betrifft und von dem Mathematiker Michel Louis Balinski gefunden wurde, ist der folgende:[31][27]

Hat ein endlicher schlichter Graph eine geradlinige Darstellung als  -dimensionaler Polytopgraph im   , so ist er notwendigerweise  -fach zusammenhängend.

Quellen und Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />

KKKategorie:Topologische Graphentheorie]] KKKategorie:Geometrische Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Steinitz, Satz von]] KKKategorie:Satz (Mathematik)|Steinitz, Satz von]]



Satz von Schnyder (unfertig)

Bearbeiten

Der Satz von Schnyder ist ein mathematischer Lehrsatz, welcher an der Nahtstelle zwischen Graphentheorie als auch der Ordnungstheorie liegt. Er geht zurück auf den niederländischen Mathematiker Walter Schnyder, der ihn im Jahre 1989 publizierte. Der Satz behandelt die Frage der Plättbarkeit endlicher schlichter Graphen aus ordnungstheoretischer Sicht und formuliert hierzu ein elegantes Kriterium.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:

Ein endlicher schlichter Graph   ist plättbar dann und nur dann, wenn für die Ordnungsdimension der zugehörigen Inzidenzordnung   die Ungleichung   gilt.

Erläuterungen

Bearbeiten

Siehe auch

Bearbeiten

Quellen und Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />


KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Schnyder, Satz von]] KKKategorie:Satz (Mathematik)|Schnyder, Satz von]]

Satz von Richardson

Bearbeiten

Der Satz von Richardson ist ein Lehrsatz der Graphentheorie, einem der Teilgebiete der Mathematik. Der Satz wurde von dem Mathematiker Moses Richardson im Jahre 1953 publiziert. Er behandelt die Frage der Existenz von Kernen in endlichen gerichteten Graphen.

Formulierung des Satzes

Bearbeiten

Er lässt sich zusammengefasst angeben wie folgt:[32][33][34]

Jeder endliche gerichtete Graphen ohne Kreise ungerader Länge besitzt mindestens einen Kern.

Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />


KKKategorie:Graphentheorie]] KKKategorie:Satz (Mathematik)|Richardson, Satz von]] KKKategorie:Satz (Graphentheorie)|Richardson, Satz von]]



Topologische Graphentheorie

Bearbeiten

Topologische Landkarte ist ein Terminus aus dem mathematischen Teilgebiet der Topologischen Graphentheorie. Der Terminus hat Bedeutung insbesondere im Zusammenhang mit Untersuchungen zu Färbungsproblemen und hier nicht zuletzt im Zusammenhang mit dem Vier-Farben-Satz und verwandten mathematischen Lehrsätzen.

Definitionen und Bezeichnungen

Bearbeiten
  • Eine topologische Landkarte   auf einer Fläche   ist ein Tripel  , wobei   und   zwei endliche Mengensysteme von Teilmengen von   sind und   ebenfalls eine endliche Menge darstellt.
    • Dabei ist   die Kantenmenge eines topologischen Graphen in   und   ist die zugehörige Knotenmenge.
    •   besteht genau aus denjenigen Punkten von  , welche für eine der Jordankurven   als Anfangs- oder Endpunkt auftreten.
    • Das Mengensystem   besteht genau aus den Wegzusammenhangskomponenten der Komplementmenge  .
  • Man bezeichnet hierbei jedes Element von   als Land, jedes Element von   als Grenzlinie und jedes Element von   als Ecke der topologischen Landkarte  .
  • Ein Punkt   ist Randpunkt eines zu der Landkarte gehörenden Landes  , wenn er dem relativen topologischen Abschluss   von   in   angehört.
  • Zwei Länder   und   von   heißen benachbart oder Nachbarländer, wenn unter den Grenzlinien von   eine vorkommt, welcher ganz aus Randpunkten sowohl von   als auch von   besteht.
  • Eine zu einer ganzen Zahl   gegebene Abbildung   nennt man  -Färbung.
    • Die Elemente von   bezeichnet man (in Einklang mit den Gepflogenheiten der Graphentheorie) als Farben.
    • Eine  -Färbung   heißt zulässig, wenn je zwei benachbarten Ländern vermöge   stets zwei verschiedene Farben zugeordnet sind.
    • Gestattet eine topologischen Landkarte   auf   für eine ganze Zahl   eine zulässige  -Färbung, jedoch keine zulässige Färbung mit weniger als   Farben, so nennt man diese ganze Zahl   die chromatische Zahl von   und bezeichnet sie mit  .
    • Bildet man über alle topologischen Landkarten auf   das Supremum       aller zugehörigen chromatischen Zahlen und ist diese ganze Zahl  , so ist dies die chromatische Zahl von  . Sie wird mit   bezeichnet.[35]

Anmerkung

Bearbeiten
  • Die untersuchten Flächen sind in aller Regel Flächen   .

Bedeutende Lehrsätze

Bearbeiten
  • Satz von Weiske: Ist   der   oder die Einheitssphäre  , so gibt es keine Landkarte mit fünf paarweise benachbarten Ländern.[36]
  • Zweifarbensatz: Ist   ein Rechteck und sind darüber hinaus die Grenzlinien einer gegebenen topologischen Landkarte   so beschaffen, dass jede von ihnen nur zwischen Randpunkten des Rechtecks verläuft oder eine innerhalb des Rechtecks verlaufene geschlossene Jordankurve darstellt, so existiert zu einer solchen topologischen Landkarte   stets eine zulässige  -Färbung.[37]
  • Vier-Farben-Satz: Ist   der   oder die Einheitssphäre  , so existiert zu jeder topologischen Landkarte auf   eine zulässige  -Färbung.
  • Fünf-Farben-Satz: Ist   der   oder die Einheitssphäre  , so existiert zu jeder topologischen Landkarte auf   eine zulässige  -Färbung.
  • Sechsfarbensatz für das Möbiusband: Das Möbiusband   hat die chromatische Zahl   und es besitzt auf ihm jede topologische Landkarte eine zulässige  -Färbung, wobei es unter diesen auch mindestens eine gibt, die nicht mit fünf Farben auskommt.[38]
  • Heawoodsche Ungleichung: Ist für eine ganze Zahl       eine geschlossene orientierbare Fläche vom Geschlecht   und ist dabei  ,[39] so existiert zu jeder topologischen Landkarte auf   eine zulässige  -Färbung. Mit anderen Worten: Für jede derartige Fläche   erfüllt die chromatische Zahl   die Ungleichung  .[40]
    • Es gilt sogar für ein solches   stets die Identitätsgleichung  .[41]
    • Insbesondere hat der Volltorus   die chromatische Zahl   und es besitzt auf ihm jede topologische Landkarte eine zulässige  -Färbung, wobei unter diesen auch solche vorkommen, die nicht mit sechs Farben auskommen.

Anmerkungen zu den Lehrsätzen

Bearbeiten
  • Der Satz von Weiske geht auf den Philologen Benjamin Gotthold Weiske (1783–1836), einen Freund des Mathematikers August Ferdinand Möbius, zurück. Die Urheberschaft für dieses Resultat wurde von dem Geometer Richard Baltzer bei Durchsicht des Nachlasses von Möbius herausgefunden. Als Baltzer über den Satz von Weiske und seine Geschichte in einem Vortrag im Jahre 1885 berichtete, setzte er dann jedoch den Irrtum in die Welt, dass sich mit Weiskes Satz bereits der Vierfarbensatz als leichte Folgerung ergibt. Richtig ist dagegen, dass im Gegensatz zu der Darstellung von Baltzer Weiskes Satz allein eine leichte Herleitung des Fünffarbensatzes ermöglicht. Der Irrtum von Baltzer wurde erst im Jahre 1959 von dem Geometer Harold Scott MacDonald Coxeter abschließend beseitigt.[36]
  • Der Vierfarbensatz wird heute zwar von vielen, jedoch keineswegs von allen Mathematikern als bewiesen angesehen. So äußerte etwa der Graphentheoretiker Horst Sachs im Jahre 1989 Bedenken gegen diese Auffassung und explizit die Meinung, dass die endgültige Lösung des Vierfarbenproblems noch aussteht.[42]
  • Dass in der heawoodschen Ungleichung sogar das Gleichheitszeichen zu gelten hat, wurde schon von Percy John Heawood vermutet und konnte dann im Jahre 1968 von den beiden Mathematikern Gerhard Ringel und John William Theodore Youngs abschließend bewiesen werden.[41]

Das Fadenproblem

Bearbeiten

Das Fadenproblem besteht in der Frage nach der Lösung folgender Aufgabe:

Es soll - wenn möglich - für eine gegebene natürliche Zahl   diejenige kleinste natürliche Zahl   bestimmt werden, für welche auf einer geschlossenen orientierbaren Fläche   des Geschlechtes   beliebig ausgewählte unterschiedliche Punkte   immer paarweise durch einfache Jordankurven in der Weise verbunden werden können, dass all diese Jordankurven einander nie überkreuzen und höchstens in den ausgewählten Punkten   treffen.[43]

Wie sich zeigt, ist das Fadenproblem lösbar und dabei ergibt sich die Formel

 .[44]

Dabei zeigt sich weiter, dass die Gültigkeit dieser Formel auch die Gültigkeit der heawoodschen Identitätsgleichung   nach sich zieht.[45]

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten

KKKategorie:Topologische Graphentheorie]]

Satz von van der Waerden (Zerlegung endlicher Mengen)

Bearbeiten

Der Satz von van der Waerden über die Zerlegung endlicher Mengen ist ein mathematischer Lehrsatz, welcher sowohl der Mengenlehre als auch der Graphentheorie zugerechnet werden kann. Er geht zurück auf den niederländischen Mathematiker Bartel Leendert van der Waerden, der ihn im Jahre 1927 publizierte. Der Satz behandelt Zerlegungen endlicher Mengen und ist engstens verwandt mit einem graphentheoretischen Satz des ungarischen Mathematikers Dénes Kőnig über reguläre bipartite Graphen aus dem Jahr 1914.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[46][47]

Gegeben seien zwei natürliche Zahlen   und dazu eine endliche Grundmenge   mit   Elementen.
Weiter gegeben seien zwei Zerlegungen   und   von   in Klassen gleicher Größe; also dergestalt, dass stets die Gleichungen   erfüllt sind.
Dann gilt:
Unter diesen Gegebenheiten besitzen   und   immer ein gemeinsames Vertretersystem; also ein Vertretersystem derart, dass jede  -Klasse und jede  -Klasse von genau einem dieser Vertreter repräsentiert wird .

Folgerung: Der Satz von Miller

Bearbeiten

B. L. van der Waerden hat seinen Satz als direkte Verallgemeinerung eines gruppentheoretischen Satzes des US-amerikanischen Mathematikers George Abram Miller gefunden und formuliert. Der millersche Satz ergibt sich, wenn man den van der Waerden'schen Satz auf die Rechts- und Linksnebenklassen der Untergruppen endlicher Gruppen anwendet. Zusammenhängend formuliert besagt der Satz von Miller also:[46][47]

In einer endlichen Gruppe gibt es für die Rechts- und Linksnebenklassen einer jeden Untergruppe stets ein gemeinsames Vertretersystem.

Zusammenhang mit bipartiten Graphen: Ein Satz von Kőnig in drei Versionen

Bearbeiten

Wie Dénes Kőnig in seiner Monographie Theorie der endlichen und unendlichen Graphen darlegt und auch B. L. van der Waerden in seiner 1927er Arbeit anmerkt, ist der van der Waerden'sche Satz gleichwertig mit einem frühen graphentheoretischen Satz von Dénes Kőnig, der sich (in moderner Formulierung) folgendermaßen angeben lässt:[48][49]

Ein endlicher regulärer bipartiter Graph besitzt stets einen  -Faktor.[50]

Über den obigen Satz hat Kőnig zum ersten Mal in 1914 auf dem Pariser Kongress für mathematische Philosophie vorgetragen und dabei zugleich auf die Gleichwertigkeit mit dem folgenden Satz hingewiesen:[51]

Jeder endliche  -reguläre bipartite Graph ( ) zerfällt in      -Faktoren.[52]

Wie Kőnig weiter zeigt, sind die beiden zuletzt zitierten Sätze ihrerseits gleichwertig mit einem von ihm im Jahre 1916 publizierten Satz, der sich formulieren lässt wie folgt:[51][53]

Laufen in jedem Knoten eines endlichen bipartiten Graphen höchstens   Kanten zusammen, so kann man die Kantenmenge so in   Klassen zerlegen, dass je zwei benachbarte Kanten stets verschiedenen Klassen angehören.

Mit anderen Worten:

Ist der Maximalgrad eines endlichen bipartiten Graphen gleich  , so ist er  -kantenfärbbar.

Dies bedeutet jedoch nichts weiter als das folgende Resultat:[54]

Für einen endlichen bipartiten Graphen sind Kantenfärbungszahl und Maximalgrad stets identisch, also:
   .

Siehe auch

Bearbeiten

Quellen und Literatur

Bearbeiten

Originalarbeiten

Bearbeiten

Monographien

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />


KKKategorie:Mengenlehre]] KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|van der Waerden, Satz von]] KKKategorie:Satz (Mathematik)|van der Waerden, Satz von]]



Satz von Rédei (Graphentheorie)

Bearbeiten

In der Graphentheorie, einem der Teilgebiete der Mathematik, ist der Satz von Rédei ein Lehrsatz, der grundlegend für die Frage der Durchlaufbarkeit von Turniergraphen ist. Der Satz geht zurück auf eine Arbeit des ungarischen Mathematikers László Rédei aus dem Jahre 1934.[55][56][57]

Formulierung des Satzes

Bearbeiten

Der rédeische Satz lässt sich zusammengefasst angeben wie folgt:

In einem endlichen Turnier mit mindestens zwei Knoten ist die Anzahl der darin vorkommenden hamiltonschen Bahnen stets eine ungerade Zahl.[58]
Demnach gibt es in jedem endlichen Turnier mindestens eine Bahn, die jeden Knoten genau einmal enthält.

Anmerkungen zum Beweis

Bearbeiten

Quellen und Literatur

Bearbeiten
  |Band=7
  |Datum=1934
  |Seiten=39–43
  |Online=[7]
  |1=Acta Scientiarum Mathematicarum [früher: Acta Litterarum ac Scientiarum (Sectio Scientiarum Mathematicarum), Szeged]]].

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />

KKKategorie:Graphentheorie]] KKKategorie:Satz (Graphentheorie)|Rédei, Satz von]] KKKategorie:Satz (Mathematik)|Satz von Rédei (Graphentheorie)]]



Satz von Kruskal

Bearbeiten

Der Satz von Kruskal ist ein Lehrsatz der Graphentheorie, einem der Teilgebiete der Mathematik. Er wurde von dem Mathematiker Joseph Bernard Kruskal im Jahre 1960 publiziert. Der Satz behandelt eine wichtige Eigenschaft der Klasse der endlichen Bäume.

Formulierung des Satzes

Bearbeiten

Der Satz lautet wie folgt:[33][60][61][62]

Die Klasse der endlichen Bäume ist durch die Quasiordnungsrelation der Bildung des topologischen Minors wohlquasigeordnet.

Verwandte Sätze

Bearbeiten

Der Satz von Kruskal wurde in den 1960-er Jahren von Crispin St. J. A. Nash-Williams auf unendliche Bäume verallgemeinert.[63][60] Einen vereinfachten Beweis beider Sätze legte Daniela Kühn im Jahre 2001 vor.[60] Der kruskalsche Satz ist eingebunden in den Problemkreis um das bedeutende Minorentheorem.

Literatur

Bearbeiten

Originalarbeiten

Bearbeiten
  • J. B. Kruskal: Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture. In: Transactions of the American Mathematical Society. Band 95, 1960, S. 210–225 ([9]). MR0111704
  • Daniela Kühn: On well-quasi-ordering infinite trees—Nash-Williams's theorem revisited. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 130, 2001, S. 401–408. MR1816801
  • C. St. J. A. Nash–Williams: On well-quasi-ordering infinite trees. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 61, 1965, S. 697–720. MR0175814
  • C. St. J. A. Nash–Williams: On better-quasi-ordering transfinite sequences. In: Mathematical Proceedings of the Cambridge Philosophical Society. Band 64, 1968, S. 273–290. MR0221949

Monographien

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />


KKKategorie:Graphentheorie]] KKKategorie:Satz (Mathematik)|Kruskal, Satz von]]



Äquivalenzsatz von Wagner

Bearbeiten

Der Äquivalenzsatz von Wagner, auch als Äquivalenzsatz von K. Wagner oder als wagnerscher Äquivalenzsatz bezeichnet, ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Er stellt eine Verbindung zwischen der Hadwiger-Vermutung und dem Vierfarbenproblem her.

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich angeben wie folgt:[61][62]

Die Vierfarbenvermutung ist mit der Hadwiger-Vermutung   äquivalent.

Anmerkung zu Einordnung des Resultats

Bearbeiten

Dem Graphentheoretiker Rudolf Halin[64] zufolge ist der Äquivalenzsatz ein überraschendes Resultat. Er sei der früheste Versuch, das Vierfarbenproblem zu „enttopologisieren“. Es werde in der Tat ... bei der Fomulierung von   keinerlei Bezug auf eine ebene Darstellung genommen. ... Es [das Vierfarbenproblem] hat auch den Anstoß dazu gegeben, die allgemeine Vermutung   auszusprechen und näher zu untersuchen.[65]

Siehe auch

Bearbeiten

Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />


KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Mathematik)|Wagner, Äquivalenzsatz von]]


Satz von Nordhaus-Gaddum

Bearbeiten

Der Satz von Nordhaus-Gaddum ist ein Lehrsatz aus dem mathematischen Teilgebiet der Graphentheorie, welcher auf eine Arbeit der beiden Mathematiker Edward Alfred Nordhaus und Jerry W. Gaddum aus dem Jahre 1956 zurückgeht. Der Satz formuliert vier grundlegende Ungleichungen über den Zusammenhang zwischen der chromatischen Zahl eines Graphen, der chromatischen Zahl des zugehörigen Komplementärgraphen und der Knotenzahl. Der Satz war Anstoß für eine Anzahl von Folgearbeiten.[66]

Formulierung des Satzes

Bearbeiten

Der Satz lautet wie folgt:[67][62][61]

Für einen endlichen schlichten Graphen   mit   Knoten und seinen Komplementärgraphen   gelten stets folgende Ungleichungen:
 
 

Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />


KKKategorie:Graphentheorie]] KKKategorie:Satz (Mathematik)|Nordhaus-Gaddum, Satz von]]



Satz von Wagner

Bearbeiten

Der Satz von Wagner ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher im Jahre 1937 von dem Mathematiker Klaus Wagner veröffentlicht wurde. Der Satz ist verwandt mit dem Satz von Kuratowski und gibt wie dieser eine Charakterisierung plättbarer Graphen.

Formulierung des Satzes

Bearbeiten
 
Abb. 1: Der Kuratowski-Graph  
 
Abb. 2: Der Kuratowski-Graph  

Der Satz lautet wie folgt:[68]

Ein endlicher schlichter Graph   ist plättbar genau dann, wenn in ihm kein Teilgraph enthalten ist, der zu einem der beiden Kuratowski-Graphen   und   kontrahierbar ist.

Anwendung

Bearbeiten

Mit dem Satz von Wagner lässt sich zeigen, dass der Petersen-Graph nicht plättbar ist.[69]

Folgerung

Bearbeiten

Die beiden Sätze von Kuratowski und Wagner führen zusammengenommen zu folgendem Resultat:[33]

Für einen endlichen schlichten Graphen   sind gleichwertig:
     :   ist plättbar.
     : In   ist keiner der beiden Kuratowski-Graphen als Minor enthalten.
     : In   ist keiner der beiden Kuratowski-Graphen als topologischer Minor enthalten.

Siehe auch

Bearbeiten

Literatur

Bearbeiten


Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />


KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Mathematik)|Wagner, Satz von]]



Satz von Wagner und Fáry

Bearbeiten

Der Satz von Wagner und Fáry, manchmal auch als Satz von Wagner oder Satz von Fáry bezeichnet, ist ein Lehrsatz aus dem mathematischen Teilgebiet der Topologischen Graphentheorie, welcher zuerst im Jahre 1936 von dem Mathematiker Klaus Wagner gefunden und dann im Jahre 1948 von dem Mathematiker István Fáry erneut gefunden wurde. Der Satz behandelt eine wichtige Eigenschaft plättbarer Graphen, die nicht zuletzt im Zusammenhang mit dem Vierfarbensatz und verwandten mathematischen Lehrsätzen von Bedeutung ist.

Formulierung des Satzes

Bearbeiten
 
Nach einem geeigneten Homoöomorphismus sind auch B und D durch eine Strecke verbunden.

Erste Version

Bearbeiten

Die erste Version des Satzes lautet wie folgt:[70]

Ist ein endlicher schlichter Graph   plättbar, so existiert sogar ein isomorpher ebener Graph   dergestalt, dass die zu den Kanten   gehörigen Jordankurven sämtlich abgeschlossene Strecken sind, die einander nie in einem inneren Punkt kreuzen, also paarweise stets höchstens einen der Knoten   gemeinsam haben.

Zweite Version

Bearbeiten

Ein ebener Graphen   der in der ersten Version genannten Art wird auch als Streckengraph oder als geradlinige Darstellung (des Graphen  ) bezeichnet. Unter Verwendung dieser Begriffe lässt sich der Satz auch folgendermaßen fomulieren:[36][62]

Jeder ebene Graph kann durch einen Homöomorphismus der euklidischen Ebene auf sich in einen Streckengraphen, also in eine geradlinige Darstellung, überführt werden.

Anmerkungen

Bearbeiten
  • Die Bedeutung des Satzes von Wagner und Fáry (in der zweiten Version) für den Vierfarbensatz geht aus einer Anmerkung hervor, die der Mathematiker Rudolf Fritsch in seiner Monographie Der Vierfarbensatz dazu macht. Fritsch schreibt, dass der Satz die endgültige Befreiung aus dem Gruselkabinett beliebiger Jordankurven bringt und den Vierfarbensatz aus den Klauen der allgemeinen Topologie löst.[71]
  • Die Vermutung, dass die Aussage des Satzes von Wagner und Fáry gelte, wurde István Fáry zufolge schon früher von dem ungarischen Mathematiker Tibor Szele geäußert.[71]

Siehe auch

Bearbeiten

Literatur

Bearbeiten

Einzelnachweise und Fußnoten

Bearbeiten

Kreferences />

KKKategorie:Topologische Graphentheorie]] KKKategorie:Satz (Mathematik)|Wagner und Fáry, Satz von]]



Topologische Landkarte

Bearbeiten

Topologische Landkarte ist ein Terminus aus dem mathematischen Teilgebiet der Topologischen Graphentheorie. Der Terminus hat Bedeutung insbesondere im Zusammenhang mit Untersuchungen zu Färbungsproblemen und hier nicht zuletzt im Zusammenhang mit dem Vier-Farben-Satz und verwandten mathematischen Lehrsätzen.

Definitionen und Bezeichnungen

Bearbeiten
  • Eine topologische Landkarte   auf einer Fläche   ist ein Tripel  , wobei   und   zwei endliche Mengensysteme von Teilmengen von   sind und   ebenfalls eine endliche Menge darstellt.
    • Dabei ist   die Kantenmenge eines topologischen Graphen in   und   ist die zugehörige Knotenmenge.
    •   besteht genau aus denjenigen Punkten von  , welche für eine der Jordankurven   als Anfangs- oder Endpunkt auftreten.
    • Das Mengensystem   besteht genau aus den Wegzusammenhangskomponenten der Komplementmenge  .
  • Man bezeichnet hierbei jedes Element von   als Land, jedes Element von   als Grenzlinie und jedes Element von   als Ecke der topologischen Landkarte  .
  • Ein Punkt   ist Randpunkt eines zu der Landkarte gehörenden Landes  , wenn er dem relativen topologischen Abschluss   von   in   angehört.
  • Zwei Länder   und   von   heißen benachbart oder Nachbarländer, wenn unter den Grenzlinien von   eine vorkommt, welcher ganz aus Randpunkten sowohl von   als auch von   besteht.
  • Eine zu einer ganzen Zahl   gegebene Abbildung   nennt man  -Färbung.
    • Die Elemente von   bezeichnet man (in Einklang mit den Gepflogenheiten der Graphentheorie) als Farben.
    • Eine  -Färbung   heißt zulässig, wenn je zwei benachbarten Ländern vermöge   stets zwei verschiedene Farben zugeordnet sind.
    • Gestattet eine topologischen Landkarte   auf   für eine ganze Zahl   eine zulässige  -Färbung, jedoch keine zulässige Färbung mit weniger als   Farben, so nennt man diese ganze Zahl   die chromatische Zahl von   und bezeichnet sie mit  .
    • Bildet man über alle topologischen Landkarten auf   das Supremum       aller zugehörigen chromatischen Zahlen und ist diese ganze Zahl  , so ist dies die chromatische Zahl von  . Sie wird mit   bezeichnet.[72]

Anmerkung

Bearbeiten
  • Die untersuchten Flächen sind in aller Regel Flächen   .

Bedeutende Lehrsätze

Bearbeiten
  • Satz von Weiske: Ist   der   oder die Einheitssphäre  , so gibt es keine Landkarte mit fünf paarweise benachbarten Ländern.[36]
  • Zweifarbensatz: Ist   ein Rechteck und sind darüber hinaus die Grenzlinien einer gegebenen topologischen Landkarte   so beschaffen, dass jede von ihnen nur zwischen Randpunkten des Rechtecks verläuft oder eine innerhalb des Rechtecks verlaufene geschlossene Jordankurve darstellt, so existiert zu einer solchen topologischen Landkarte   stets eine zulässige  -Färbung.[37]
  • Vier-Farben-Satz: Ist   der   oder die Einheitssphäre  , so existiert zu jeder topologischen Landkarte auf   eine zulässige  -Färbung.
  • Fünf-Farben-Satz: Ist   der   oder die Einheitssphäre  , so existiert zu jeder topologischen Landkarte auf   eine zulässige  -Färbung.
  • Sechsfarbensatz für das Möbiusband: Das Möbiusband   hat die chromatische Zahl   und es besitzt auf ihm jede topologische Landkarte eine zulässige  -Färbung, wobei es unter diesen auch mindestens eine gibt, die nicht mit fünf Farben auskommt.[38]
  • Heawoodsche Ungleichung: Ist für eine ganze Zahl       eine geschlossene orientierbare Fläche vom Geschlecht   und ist dabei  ,[73] so existiert zu jeder topologischen Landkarte auf   eine zulässige  -Färbung. Mit anderen Worten: Für jede derartige Fläche   erfüllt die chromatische Zahl   die Ungleichung  .[40]
    • Es gilt sogar für ein solches   stets die Identitätsgleichung  .[41]
    • Insbesondere hat der Volltorus   die chromatische Zahl   und es besitzt auf ihm jede topologische Landkarte eine zulässige  -Färbung, wobei unter diesen auch solche vorkommen, die nicht mit sechs Farben auskommen.

Anmerkungen zu den Lehrsätzen

Bearbeiten
  • Der Satz von Weiske geht auf den Philologen Benjamin Gotthold Weiske (1783–1836), einen Freund des Mathematikers August Ferdinand Möbius, zurück. Die Urheberschaft für dieses Resultat wurde von dem Geometer Richard Baltzer bei Durchsicht des Nachlasses von Möbius herausgefunden. Als Baltzer über den Satz von Weiske und seine Geschichte in einem Vortrag im Jahre 1885 berichtete, setzte er dann jedoch den Irrtum in die Welt, dass sich mit Weiskes Satz bereits der Vierfarbensatz als leichte Folgerung ergibt. Richtig ist dagegen, dass im Gegensatz zu der Darstellung von Baltzer Weiskes Satz allein eine leichte Herleitung des Fünffarbensatzes ermöglicht. Der Irrtum von Baltzer wurde erst im Jahre 1959 von dem Geometer Harold Scott MacDonald Coxeter abschließend beseitigt.[36]
  • Der Vierfarbensatz wird heute zwar von vielen, jedoch keineswegs von allen Mathematikern als bewiesen angesehen.[74]
  • Dass in der heawoodschen Ungleichung sogar das Gleichheitszeichen zu gelten hat, wurde schon von Percy John Heawood vermutet und konnte dann im Jahre 1968 von den beiden Mathematikern Gerhard Ringel und John William Theodore Youngs abschließend bewiesen werden.[41]

Das Fadenproblem

Bearbeiten

Das Fadenproblem besteht in der Frage nach der Lösung folgender Aufgabe:

Es soll - wenn möglich - für eine gegebene natürliche Zahl   diejenige kleinste natürliche Zahl   bestimmt werden, für welche auf einer geschlossenen orientierbaren Fläche   des Geschlechtes   beliebig ausgewählte unterschiedliche Punkte   immer paarweise durch einfache Jordankurven in der Weise verbunden werden können, dass all diese Jordankurven einander nie überkreuzen und höchstens in den ausgewählten Punkten   treffen.[43]

Wie sich zeigt, ist das Fadenproblem lösbar und dabei ergibt sich die Formel

 .[75]

Dabei zeigt sich weiter, dass die Gültigkeit dieser Formel auch die Gültigkeit der heawoodschen Identitätsgleichung   nach sich zieht.[45]

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten

Kreferences />

KKKategorie:Topologische Graphentheorie]]

Einzelnachweise und Fußnoten

Bearbeiten
  1. a b A. Hajnal, J. Surányi: Über die Auflösung von Graphen in vollständige Teilgraphen. In: Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae. Sectio Mathematica. Band 1, 1958, S. 113–121. Referenzfehler: Ungültiges <ref>-Tag. Der Name „:0“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert.
  2. a b Stasys Jukna: Extremal Combinatorics. 2011, S. 56 ff., S. 63.
  3. László Lovász: Combinatorial Problems and Exercises. 1979, S. 68, S. 395.
  4. Stasys Jukna: Extremal Combinatorics. 2011, S. 25–26.
  5. Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise . 2018, S. 224–225.
  6. Stasys Jukna: Extremal Combinatorics. 2011, S. 9.
  7. Rudolf Halin: Graphentheorie. 1989, S. 110
  8. Robin J. Wilson: Einführung in die Graphentheorie. 1976, S. 111–112
  9. Frank Harary: Grapentheorie. 1974, S. 220
  10. Halin, op. cit., S. 110, 304
  11. Claude Berge: Graphs and Hypergraphs. 1973, S. 124.
  12. John Clark, Derek Allan Holton: Graphentheorie. 1994, S. 137.
  13. Lutz Volkmann: Fundamente der Graphentheorie. 1996, S. 117.
  14. a b I. N. Bronstein, K. A. Semendjajev u. a.: Taschenbuch der Mathematik. 2016, S. 420.
  15. Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, S. 390 ff.
  16. a b Jonathan L. Gross, Jay Yellen (Hrsg.): Handbook of Graph Theory. 2004, S. 1105.
  17. Rudolf Halin: Graphentheorie. 1989, S. 199ff, 207, 209
  18. Halin, op. cit., S. 209-213
  19. a b c Hansjoachim Walther, Heinz-Jürgen Voß: Über Kreise in Graphen. 1974, S. 26
  20. Øystein Ore: The Four-Color Problem. 1967, S. 74
  21. Ore, op. cit., S. 105–108
  22. Das bedeutet etwa für den Beweis des Vierfarbensatzes, dass im Rahmen eines Widerspruchsbeweises das angenommene kleinst Gegenbeispiel als ebener nicht  -fach zusammenhängender Streckengraph vorausgesetzt werden kann.
  23. Frank Harary: Grapentheorie. 1974, S. 117–118
  24. a b Harary, op. cit., S. 118
  25. Harary, op. cit., S. 116
  26. In diese Begriffsfassung geht entscheidend der Satz von Wagner und Fáry ein.
  27. a b Branko Grünbaum: Polytopal Graphs in: Studies in Graph Theory. Part II (Hrsg. D. R. Fulkerson), 1975, S. 203
  28. Lowell W. Beineke, Robin J. Wilson: Topics in Topological Graph Theory, 2009, S. 11
  29. Frank Harary: Grapentheorie. 1974, S. 115
  30. Grünbaum, op. cit., S. 204
  31. M. L. Balinski: On the graph structure of convex polyhedra in n-space. in: Pacific J. Math. 11, S. 431–434
  32. Jørgen Bang-Jensen, Gregory Z. Gutin: Digraphs. 2010, S. 119–120
  33. a b c Reinhard Diestel: Graph Theory. 2005, S. 135 Referenzfehler: Ungültiges <ref>-Tag. Der Name „RD-1“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert.
  34. Gunther Schmidt, Thomas Ströhlein: Relationen und Graphen. 1989, S. 188
  35. Die chromatische Zahl   ist zu unterscheiden von der Euler-Charakteristik von  , obwohl für beide Zahlen derselbe griechische Buchstabe als Bezeichner auftritt.
  36. a b c d e Rudolf Fritsch: Der Vierfarbensatz. 1994, S. 25–26, 128 Referenzfehler: Ungültiges <ref>-Tag. Der Name „RF-GF-1“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert.
  37. a b K. P. Müller, H. Wölpert: Anschauliche Topologie. 1976, S. 67
  38. a b Müller, Wölpert, op. cit., S. 148–149
  39.   ist die Gaußklammerfunktion.
  40. a b Gerhard Ringel: Das Kartenfärbungsproblem. in: Selecta Mathematica III 1971, S. 30 ff., 45-47 Referenzfehler: Ungültiges <ref>-Tag. Der Name „GR-1“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert.
  41. a b c d Ringel, op. cit., S. 31
  42. Lutz Volkmann: Fundamente der Graphentheorie. 1996, S. 254–255
  43. a b Ringel, op. cit., S. 32
  44.   ist die Aufrundungsfunktion.
  45. a b Ringel, op. cit., S. 32–33
  46. a b Bartel L. van der Waerden: Ein Satz ... . in: Abh. Math. Sem. Univ. Hamburg 5, S. 185–188
  47. a b Dénes König: Theorie der endlichen und unendlichen Graphen. 1986, S. 171 ff., 176–177
  48. van der Waerden, a. a. O. , S. 187
  49. König, op. cit. S. 171,176
  50. Wie Rudolf Halin in seiner Graphentheorie I anmerkt (S. 166), fallen für bipartite Graphen die Begriffe „ -Faktor“ und „vollständige Paarung“ zusammen.
  51. a b König, op. cit. S. 170–171
  52. Die dem Graphen und seinen   Faktoren zugrundeliegende Knotenmenge ist dabei dieselbe, während die Faktorisierung eine Zerlegung der Kantenmenge in   Teilmengen bewirkt.
  53. Dénes König: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. In: Mathematische Annalen, Bd. 77, 1916, S. 453–456
  54. Reinhard Diestel: Graph Theory. 2005, S. 119
  55. a b Rudolf Halin: Graphentheorie I. 1980, S. 205 ff., 220–221
  56. Dénes König: Theorie der endlichen und unendlichen Graphen. 1986, S. 29–31
  57. a b Horst Sachs: Einführung in die Theorie der endlichen Graphen. 1971, S. 164–166
  58. Horst Sachs (op. cit., S. 165) bezeichnet eine solche hamiltonsche Bahn auch als vollständige Bahn.
  59. Vgl. Publicationes Mathematicae Debrecen, Bd. 13, 1966, S. 145 ff.
  60. a b c Egbert Harzheim: Ordered Sets. 2005, S. 245
  61. a b c Klaus Wagner: Graphentheorie. 1970, S. 172 ff., 178 Referenzfehler: Ungültiges <ref>-Tag. Der Name „KW-1“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert.
  62. a b c d Rudolf Halin: Graphentheorie I. 1980, S. 116 ff. Referenzfehler: Ungültiges <ref>-Tag. Der Name „RH-1“ wurde mehrere Male mit einem unterschiedlichen Inhalt definiert.
  63. Diestel, op. cit., S. 354
  64. Halin ist ein Schüler von Klaus Wagner und hat den ersten Band seiner Graphentheorie diesem in Dankbarkeit gewidmet.
  65. Halin, op. cit., S. 274
  66. Vgl. etwa Liste im MathSciNet!
  67. Frank Harary: Grapentheorie. 1974, S. 137-138
  68. Dieter Jungnickel: Graphs, Networks and Algorithms. 2008, S. 23-24
  69. Jungnickel, op. cit., S. 24
  70. Nora Hartsfield, Gerhard Ringel: Pearls in Graph Theory. 1990, S. 166-167
  71. a b Fritsch, op. cit., S. 107
  72. Die chromatische Zahl   ist zu unterscheiden von der Euler-Charakteristik von  , obwohl für beide Zahlen derselbe griechische Buchstabe als Bezeichner auftritt.
  73.   ist die Gaußklammerfunktion.
  74. Siehe Vier-Farben-Satz#Kritik
  75.   ist die Aufrundungsfunktion.

Anmerkungen

Bearbeiten
  1. Wie Stasys Jukna hervorhebt, ist der Mantel’sche Satz ein schönes Resultat (beautiful result), für den (mindestens) vier verschiedene Beweise existieren.
  2. Nimmt man für geradzahliges   den vollständig bipartiten Graph   , so zeigt sich, dass diese Ungleichung scharf ist.
  3.   ist die Ganzzahl-Funktion.
  4. Auf ähnlichen Formeln beruht auch der Beweis zum Lemma von Corrádi. Die in beiden Fällen wesentlich herangezogene Beweismethode ist die Methode der doppelten Abzählung (englisch double counting).
  5. Diese Formel lässt sich als eine Verallgemeinerung des Handschlaglemmas auffassen.