MATH 4022  Introduction to Graph Theory
Fall 2010  Tuesday/Thursday 13:3015: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. Matrixtree Theorem using BinetCauchy
Theorem.

Lecture 8:
The MatrixTree 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
KonigEgervary.

Lecture 11:
Dilworth's Theorem via KonigEgervary Theorem. Mirsky's Theorem (dual
Dilworth Theorem).

Lecture 12:
Birkhoff/vonNeumann Theorem. Sperner's Theorem. Stable Matchings
(GaleShapley Theorem).

Lecture 13:
Theorems of Tutte, Petersen and GallaiMilgram.

Lecture 14:
TutteBerge Formula. Tutte's matrix condition for existence of perfect
matching.
Connectivity

Lecture 15:
kconnected subgraphs in dense graphs (Mader's Theorem). Menger's Theorem.

Lecture 16:
Variant's of Menger's Theorem (edges, vertices and global). Structure of
2connected graphs; Block and Ear Decompositions.

Lecture 17:
Circulations, Flows and the MaxFlowMinCut Theorem. Relation to Menger's
Theorem.
Hamilton Cycles

Lecture 18:
Hamilton Cycles and the Theorems of Dirac and ChvatalErdos.

Lecture 19:
Hamiltonian degree sequences (Chvatal's Theorem). Ore's Theorem.
DeBruijn sequences.
Coloring

Lecture 20:
Vertex and edge colorings and their relation to maxdegree

Lecture 21:
Chromatic number and degeneracy. Edgecoloring bipartite graphs (Konig's
Theorem).

Lecture 22:
Vizing's Theorem. Basic properties of kcritical graphs.

Lecture 23:
Structure of non 3connected kcritical graphs. Brook's Theorem.

Lecture 24:
Trianglefree 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. Highdegree minors in sparse graphs of high girth.
Planar Graphs

Lecture 28:
Planar graph, Dual graph, Euler formula. Comments on Kuratowski's Theorem and the 4Color Theorem.

Lecture 29:
The 5Color Theorem and Tait's "proof" of the 4Color Theorem.