Benutzer:Schojoha/Spielwiese/Graphentheorie

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Zum Satz von Hajnal und Surányi

[Bearbeiten | Quelltext 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 .

Satz von Mantel

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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.

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) .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

rreferences />

rreferences group="A" />

KKKategorie:Satz (Graphentheorie)|Mantel]]

Satz von Ghouila-Houri

[Bearbeiten | Quelltext 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 | Quelltext 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.

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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

rreferences />

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

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 | Quelltext 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.
  • 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.
  • 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]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

Kreferences />

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



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 | Quelltext 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 | Quelltext bearbeiten]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

Kreferences />

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

Satz von Tutte (Hamiltonkreisproblem)

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />

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

Satz von Battle-Harary-Kodama

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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.

Quellen und Literatur

[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


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

Satz von Richardson

[Bearbeiten | Quelltext 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 | Quelltext 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.

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


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



Topologische Graphentheorie

[Bearbeiten | Quelltext 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 | Quelltext 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.
  • 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]
  • Die untersuchten Flächen sind in aller Regel Flächen .

Bedeutende Lehrsätze

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

KKKategorie:Topologische Graphentheorie]]

Satz von van der Waerden (Zerlegung endlicher Mengen)

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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:
 .

Quellen und Literatur

[Bearbeiten | Quelltext bearbeiten]

Originalarbeiten

[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Quellen und Literatur

[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Kreferences />

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



Satz von Kruskal

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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.

Originalarbeiten

[Bearbeiten | Quelltext 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

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


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



Äquivalenzsatz von Wagner

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


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


Satz von Nordhaus-Gaddum

[Bearbeiten | Quelltext 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 | Quelltext 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:

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


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



Satz von Wagner

[Bearbeiten | Quelltext 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 | Quelltext 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.

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

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.


Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />


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



Satz von Wagner und Fáry

[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]
Nach einem geeigneten Homoöomorphismus sind auch B und D durch eine Strecke verbunden.

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.

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.
  • 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]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext bearbeiten]

Kreferences />

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



Topologische Landkarte

[Bearbeiten | Quelltext 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 | Quelltext 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.
  • 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]
  • Die untersuchten Flächen sind in aller Regel Flächen .

Bedeutende Lehrsätze

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]

Kreferences />

KKKategorie:Topologische Graphentheorie]]

Einzelnachweise und Fußnoten

[Bearbeiten | Quelltext 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.
  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.