22C:137, 22M:152 Theory of Graphs: Schedule and Plans
Part I: Connectivity, Matching, Flows, and Matroid theory
 1/18: Introduction to kconnectivity, Mader's 1972 theorem
connecting vertex degree and connectivity (pages 1112), biconnectivity,
blockcut point trees.
 1/20: Menger's theorems, proof from first principles
by Bohme, Goring, and Harant (1999) (pages 5051).
 1/25: No class.
 1/27: Finished up proofs of Menger's theorems. Introduction to
flow networks and flows, the maxflow problem.
 2/1: The FordFulkerson proof (1956) of
the maxflow mincut theorem (pages 125128), a second proof of Menger's
theorems using the maxflow mincut thorem.
 2/3: Matching in bipartite graphs, KonigEgervary theorem (1931)
and its proof from Menger's theorem, Hall's marriage theorem (1935) and its
proof from KonigEgervary theorem.
 2/8: Tutte's 1factor theorem (1947) and proof (page 35).
statement and motivation of of Mader's Hpath theorem (1978).
Homework 1 assigned. Due 3/1.
 2/10: Statement and motivation of of Mader's Hpath theorem (1978).
Implications of Mader's theorem.
 2/15: Proof of Tutte's 1factor theorem from Mader's theorem.
Other implications of Mader's theorem.
Introduction to the theorem of Tutte and NashWilliams (1961) showing
necessary and sufficient conditions on the existence of edgedisjoint
spanning trees (pages 5861).
 2/17: Completion of the proof of the Tutte/NashWilliams
on edgedisjoint spanning trees.

2/22:
Minimum cost kconnected spanning subgraph problem.
Approximation algorithms. Introduction to Matroid theory.

2/24: Examples of matroids. Greedy algorithm for
finding a maximum weight independent set in a matroid.

3/3: Transversal matroids, graphic matroids, cographic matroids.
Motivation for Edmond's matroid intersection algorithm and matroid
intersection theorem.

3/8: Proof of correctness of Edmond's polytime algorithm
for matroid intersection. Edmond's matroid intersection theorem.

3/10:
Completed the proof of correctness of Edmond's matroid intersection theorem.
Showed that Konig's matching theorem follows immediately from
Edmond's matroid intersection theorem. Also showed how the Hamiltonian
path problem in directed graphs reduces to the problem of finding the
largest common independent set in three matroids.
Part II: Graph Coloring

3/22: Graph coloring. Brook's theorem, Konig's Theorem, and
Vizing's theorem. Proof of Brook's theorem.
Midterm handed out.

3/24: Proofs of Konig's Theorem and Vizing's theorem.
Midterm due.

3/29: 5colorability of planar graphs.
A brief history of the 4color theorem.

3/31 Introduction to list coloring.
Thomassen's theorem on the 5choosability of planar graphs.

4/5 Galvin's theorem that proves the list coloring conjecture
for bipartite graphs.

4/8 Trianglefree graphs with large chromatic number (Mycielski's
construction). Erdos' 1959 probabilistic construction of graphs with large
girth and large chromatic number.

4/12 Erdos' construction of graphs with large girth and large
chromatic number. Introduction to perfect graphs.

4/14 Examples of perfect graphs: interval graphs and
chordal graphs.

4/19 A proof by Lovasz of the perfect graph theorem.
Polyhedral results on perfect graphs.

4/21 Plan: Ellipsoid algorithm for optimally coloring perfect graphs in
polynomial time.
Part III: Random Graphs and the Probabilistic Method