
Graphs and Coloring
Zachary Abel teaches Lecture 11 of MIT's 6.1200J Mathematics for Computer Science, covering graph theory fundamentals and the coloring problem. The lecture works through different types of graphs and the definitions that make them useful for modeling scheduling conflicts, communication networks, and search problems. Abel develops graph coloring as a way to assign labels so that connected vertices never share a color, building toward the chromatic number and the kinds of proofs used to bound it. Expect board work with definitions, theorems, and worked examples rather than slides, in the standard MIT OCW recorded-lecture format. Running 81 minutes, the lecture assumes the discrete math groundwork laid in earlier sessions of the course and fits into the broader unit on graph theory that follows it with topics like matching and connectivity.