22C:137, 22M:152 Theory of Graphs: Schedule and Plans
Part I: Connectivity, Matching, Flows, and Matroid theory
- 1/18: Introduction to k-connectivity, Mader's 1972 theorem
connecting vertex degree and connectivity (pages 11-12), biconnectivity,
block-cut point trees.
- 1/20: Menger's theorems, proof from first principles
by Bohme, Goring, and Harant (1999) (pages 50-51).
- 1/25: No class.
- 1/27: Finished up proofs of Menger's theorems. Introduction to
flow networks and flows, the max-flow problem.
- 2/1: The Ford-Fulkerson proof (1956) of
the max-flow min-cut theorem (pages 125-128), a second proof of Menger's
theorems using the max-flow min-cut thorem.
- 2/3: Matching in bipartite graphs, Konig-Egervary theorem (1931)
and its proof from Menger's theorem, Hall's marriage theorem (1935) and its
proof from Konig-Egervary theorem.
- 2/8: Tutte's 1-factor theorem (1947) and proof (page 35).
statement and motivation of of Mader's H-path theorem (1978).
Homework 1 assigned. Due 3/1.
- 2/10: Statement and motivation of of Mader's H-path theorem (1978).
Implications of Mader's theorem.
- 2/15: Proof of Tutte's 1-factor theorem from Mader's theorem.
Other implications of Mader's theorem.
Introduction to the theorem of Tutte and Nash-Williams (1961) showing
necessary and sufficient conditions on the existence of edge-disjoint
spanning trees (pages 58-61).
- 2/17: Completion of the proof of the Tutte/Nash-Williams
on edge-disjoint spanning trees.
Minimum cost k-connected 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
3/8: Proof of correctness of Edmond's poly-time algorithm
for matroid intersection. Edmond's matroid intersection theorem.
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.
3/29: 5-colorability of planar graphs.
A brief history of the 4-color theorem.
3/31 Introduction to list coloring.
Thomassen's theorem on the 5-choosability of planar graphs.
4/5 Galvin's theorem that proves the list coloring conjecture
for bipartite graphs.
4/8 Triangle-free 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
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
Part III: Random Graphs and the Probabilistic Method