Proposition 0.2.2: Beziehung Minimalgrad, Epsilon
Mader (1972)
Jeder Graph mit d(G) >= 4k hat einen (k+1)-zusammenhängenden Teilgraphen H
Satz 1.1.1 (König 1931)
Proposition 2.3.6: Gebiete in einem 2-zsh., ebenen Graphen
Proposition 3.2.7: Gebiete in einem 3-zsh., ebenen Graphen
Definition Fächer, Satz Fächermenger, Beweisskizze
Satz 4.1.3 (Grötzsch 1959)
Jeder ebene Graph, der kein Dreieck enthält, ist 3-färbbar.
Satz 2.3.1 (Menger 1927)
magere Graphen, dichte Graphen
Kantendichte
Graphen, deren Kantenzahl größenordnungsmäßig höchstens linear in ihrer Eckenzahl ist, heißen mager.
Graphen, deren Kantenzahl größenordnungsmäßig quadratisch in der Anzahl ihrer Ecken ist, nennt man dicht.
Die Zahl ||G|| / (|G| über 2), der tatsächlich vorhandene Anteil seiner potentiellen Kanten, ist die Kantendichte von G.
Satz 4.2.5 (Erdös 1959)
Proposition 6.3.1: Äquivalenz zu “kantenmaximal ohne K^4-Minor”
Korollar 9.2.3: Erdös für Zusammenhang, Durchschnittsgrad, Minimalgrad
Minimalgrad treibt Durchschnittsgrad nach oben
Satz 0.4.3 (Mader 1972) Durchschnittsgrad treibt Zusammenhang nach oben
Kantenraum
Standardbasis
Skalarprodukt
Dualer Unterraum
Dimensionsformel
cycle space
cyclomatic number
two equivalents: elements of the cycle space
cut, atomic cut, bond
cuts in a connected graph
cut space
generating a cut
cycle space and cut space correlation
fundamental cycle, fundamental cut
theorem
Inzidenzmatrix, Beziehung zu cut und cycle space
2 definitions block
schlichte Kantenmenge
schlichte Basis
(sparse)
topologisches Dual
G hat genau dann ein Dual, wenn G zusammenhängend ist.
geodesic
a cycle C is geodesic if for every two vertices of C their distance in G equals their distance in C
packing-covering theorem
Kreise und Minimalschnitte duale Graphen
kombinatorisch dual
proposition for cut and cycle space in this context
Whitney’s Theorem
circulation on G
H-flow
Theorem: number of H-flows
Corollary
k-flow
flow number
proposition for 2-flows
proposition for 3-flows
flow numbers of K_n’s
proposition for 4-flows
Theorem (flows and colourings)
Lemma (circulations and oriented cycles)
snark
5/4/3-flow conjecture
6-flow Theorem (Seymour)
When do we have K^r as topological minor?
density of a pair (X, Y)
e-regularity of a pair (A, B)
e-regular partition
regularity lemma
Proof sketch regularity lemma
blow-up Lemma
number of edges in the Turan-Graph
Erdös-Stone Theorem
Sketch proof Erdös-Stone Theorem
Ramsey’s Theorem (standard)
Ramsey’s number R(r)
Ramsey’s Theorem (hypergraphs, c-colourings)
Ramsey’s number R(k, c, r)
Ramsey number R(H)
Theorem about that
Ramsey graph
Theorem about this
embeddings between bipartite graphs (definition)
Theorem
Lemma: bipartite Ramsey graph
Induced Ramsey Theorem proof construction (rough idea)
well-quasi ordering
equivalence
graph minor theorem
graph minor theorem for trees
When is X distinguished from Y?
Lemma for that
tree-width duality theorem
bramble number
chordal graphs
two equivalences
Grid Theorem
Forb ( H1, H2, …, Hk) definition
externally k-connected
k-weave
Lemma about k-weaves
crossing wel
Last changed6 days ago
