Course Descriptions

16:642:581 - Graph Theory

Jeffry Kahn

Course Description:

The course is intended to provide a (reasonably high level) introduction to basic topics in graph theory, including:


matching theory and minimax theorems;

coloring problems;


planar graphs;

extremal graph theory, Ramsey theory, random graphs (some of this is also covered in 582-3, but we'll try to avoid a lot of overlap);

polyhedral issues if time allows.


Diestel, Graph Theory (Optional: most of what we cover will be in Diestel, but we won't really follow the book.)


The course is mostly self-contained, though some previous combinatorics, linear algebra, rudimentary probability are all occasionally helpful. See me if in doubt.

Schedule of Sections