Inhalt GT I

Inhalt GT I
Kapitel 0
Sie sollten sicher mit den grundlegenden Definitionen aus 0.1–0.8 umgehen
können. Insbesondere Teilgraph vs Untergraph, Minimal-, Maximal- und
Durchschnittsgrad, Wege, Bäume, Kreise, vollständige Graphen, bipartite
Graphen, Zusammenhang, Kantenzusammenhang und Minoren vs topologische Minoren.
Sätze: 0.2.1, 0.2.2, 0.3.1–0.3.5, 0.4.2, 0.4.3, 0.5.1, 0.5.3, 0.5.5 (i), 0.5.6,
0.6.1, 0.7.2, 0.8.1
Kapitel 1
Die Sätze von König, der Heiratssatz und Satz 1.2.1 sind echte Klassiker
der Graphentheorie. Wichtige Techniken sind die Verbesserungswege aus
dem 1. Beweis des Heiratssatzes und Wege, deren Kanten zwischen zwei
Paarungen alternieren, wie sie im Beweis von 1.2.1 vorkommen (und auch
bei Kantenfärbungen).
Sätze: 1.1.1–1.1.5, 1.2.1, 1.2.2, 1.5.1, 1.5.2
Kapitel 2
Wichtig sind in diesem Kapitel Komponenten, Blöcke und die Konstruktion 2-zusammenhängender Graphen (2.1.1). Sie sollten auch die Varianten
des Satzes von Menger beherrschen (also Wege zwischen zwei Eckenmengen, kreuzungsfreie Wege zwischen zwei Ecken, Wegefächer, kantendisjunkte
Wege).
Sätze: 2.1.1, 2.1.4, 2.2.1,2.2.2, 2.3.1, 2.3.4–2.3.6
Kapitel 3
Sie sollten zwar formal ebene Graphen und Gebiete definieren können, die
elementartopologischen Argumente (Kap 3.1 und 3.2.2) sind aber nicht so
wichtig. Die Eulerformel und Kuratowski sind hingegen essentiell.
Sätze: 3.1.1–3.1.3, 3.2.1–3.2.4, 3.2.6, 3.2.8–3.2.11, 3.4.1–3.4.7
Kapitel 4
Sie sollten sich den (möglicherweise fehlenden) Zusammenhang zwischen chromatischer Zahl und anderen Grapheninvarianten klar machen. Wichtige
Technik: umfärben von zweifarbigen Untergraphen Hblau,rot .
Sätze: 4.1.1, 4.1.2, 4.2.2–4.2.5, 4.3.1, 4.3.2, 4.4.1–4.4.4
1
Kapitel 5
Was ist ein Fluss in einem Netzwerk? Das max-flow min-cut theorem muss
man kennen.
Sätze: 5.2.1–5.2.3
Kapitel 6
Wie groß muss der Durchnittsgrad sein, um einen K r als (topologischen)
Minor zu erzwingen? Wieviele Kanten braucht man, einen K r als Teilgraph
zu garantieren? Warum ist die Hadwiger-Vermutung plausibel, und warum
wird sie nicht bereits durch die Ergebnisse in Kapitel 6.2 impliziert?
Sätze: 6.1.1, 6.1.2, 6.1.3, 6.2.2 (4.Auflage), 6.2.2, 2.5.1, 6.2.1 (ohne Beweis), 6.3.1, 6.3.3, 6.3.4, 6.3.5, 6.3.7
Kapitel 7
Was ist die Ramseyzahl eines Graphen? Wieso folgt K r ⊆ G oder K r ⊆ G
nicht bereits aus dem vorigen Kapitel? Wie groß ist (größenordnungsmäßig)
R(K r )?
Sätze: 7.1.1, 7.2.1, 7.2.3
Kapitel 8
Was ist ein Hamiltonkreis? Wie kann man einen Hamiltonkreis erzwingen,
und wie geht das nicht? Was bedeutet der Satz von Chvátal?
Sätze: 8.1.1, Robustheitsvermutung, 8.1.3, 8.2.1
Kapitel 9
Was ist der Wahrscheinlichkeitsraum G(n, p)? Welche Art von Resultaten
kann man mit der probabilistischen Methode erzielen?
Sätze: 9.1.2–9.1.5, 9.2.1, 9.2.2, 9.3.2, 9.3.3, 9.3.5
Kürteil für Bachelorprüfung
Für die Prüfung suchen Sie sich bitte zwei der nachfolgend aufgelisteten Sätze
aus und bereiten deren Beweis so vor, dass Sie sie, unter Weglassen einiger
Details, innerhalb von etwa 5 Minuten präsentieren können. Sie sollten die
Beweise im Idealfall komplett durchdringen und eine Grundidee erkennen
und benennen können. Desweiteren sollte Ihnen klar sein, wo die Grenzen
der Beweise sind und warum sie nicht vereinfacht werden können.
2
Sätze für den Kürteil:
0.4.3 Satz von Mader
1.1.1 Satz von König
1.1.2 Hall’sche Heiratssatz
1.1.4 stabile Paarungen von Gale & Shapely
1.5.1 Wegüberdeckungen, Gallai & Milgram
2.2.1 Kantenkontraktion in 3-zusammenhängenden Graphen
2.3.1 Satz von Menger
2.5.1 hoher Durchschnittsgrad erzwingt T K r
3.4.3 Satz von Kuratowski für 3-zusammenhängende Graphen
4.1.2 5-Farbensatz
4.2.4 Satz von Brooks
4.4.2 5-Listenfarbensatz
5.2.2 max-flow min-cut
6.2.2 (4.Auflage) hoher Durchschnittsgrad erzwingt K r -Minor
7.1.1 Satz von Ramsey
8.2.1 Satz von Chvátal – nur die ⇐-Richtung
9.3.5 Der Rado-Graph – nur (i)
3