MATH 4022 - Introduction to Graph Theory
Fall 2010 - Tuesday/Thursday 13:30-15:00
Sperner's Lemma and Brouwer's Fixed Point Theorem.
Paths, Cycles, Girth, Diameter and their relation to vertex degrees. The
Edge and vertex connectivity. Cut vertices, bridges and Trees.
Bipartite graphs and odd cycles. Whitney's Theorem. Euler paths and cycle.
Cayley's Formula and Matrix Tree Theorem
Cayley formula using recursion and using bijections (Prufer Codes).
Cayley formula by direct counting. Matrix-tree Theorem using Binet-Cauchy
The Matrix-Tree Theorem for directed rooted spanning trees (Tutte).
Matching and Covering
Theorems of Hall and Berge.
Hall's Theorem using augmenting paths. Applications of Hall's Theorem:
defect Hall Theorem, Marriage Theorem, and the Theorems of Petersen and
Dilworth's Theorem via Konig-Egervary Theorem. Mirsky's Theorem (dual
Birkhoff/von-Neumann Theorem. Sperner's Theorem. Stable Matchings
Theorems of Tutte, Petersen and Gallai-Milgram.
Tutte-Berge Formula. Tutte's matrix condition for existence of perfect
k-connected subgraphs in dense graphs (Mader's Theorem). Menger's Theorem.
Variant's of Menger's Theorem (edges, vertices and global). Structure of
2-connected graphs; Block and Ear Decompositions.
Circulations, Flows and the Max-Flow-Min-Cut Theorem. Relation to Menger's
Hamilton Cycles and the Theorems of Dirac and Chvatal-Erdos.
Hamiltonian degree sequences (Chvatal's Theorem). Ore's Theorem.
Vertex and edge colorings and their relation to max-degree
Chromatic number and degeneracy. Edge-coloring bipartite graphs (Konig's
Vizing's Theorem. Basic properties of k-critical graphs.
Structure of non 3-connected k-critical graphs. Brook's Theorem.
Triangle-free graphs of high chromatic number. The Conjectures of Hajos and Hadwiger. Proof for k=4.
Theorems of Ramsey, Schur and Turan.
Graph Ramsey Numbers of Clique/Tree and Induced Star/Path/Clique. Topological Minors in sparse graphs .
Highly connected graphs are highly linked. High-degree minors in sparse graphs of high girth.
Planar graph, Dual graph, Euler formula. Comments on Kuratowski's Theorem and the 4-Color Theorem.
The 5-Color Theorem and Tait's "proof" of the 4-Color Theorem.