MTH 255: Graph Theory

This course surveys graph theory. A graph is just a set of vertices some pairs of which are joined by edges. You've seen a minimum weight spanning tree (a cheapest connected graph) in Discrete Math, possibly Chemistry, Biology, or Computer Science. We will look at matching, coloring, planarity, connectivity and communication reliability, and Hamiltonicity. Typical problems include (i) scheduling final exams, (ii) delivering mail, (iii) determining most likely evolutionary ancestors, and (iv) pairing up roommates. (By the way these problems all have fundamentally different answers.)