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