Math 1230

time/place: Tu-Th 1:00-2:40 Barus&Holley 159
instuctor: Prof. Rich Schwartz
my office hours: TBA

course summary: This is an upper level course on graph theory. We'll start with the basics and try to cover some of the well known theorems in the subject.

text: Introduction to Graph Theory (2nd ed.) by Douglas B. West

• homework: 20%
• midterm 1: 20%
• midterm 2: 20%
• final exam: 40%

homework: I will assign homework each Tuesday
and collect it the following Tuesday. No late HW.

notes topics covered:
• Chapter 1:
• walks, paths, and trails
• Eulerian circuits
• degree sequences
• directed graphs; deBruijn sequences
• Extra topic: Sperner's Lemma
• Extra topic: Random graphs; the Rado graph
• Chapter 2:
• spanning trees
• min weight spanning trees; Kruskal's Algorithm
• Matrix Tree Theorem
• Prufer codes; tree enumeration
• Extra topic: Cayley graphs; Conway's Tribones
• Chapter 3:
• Hall's matching criterion; Marriage Theorem
• augmenting path algorithm
• weighted matching; Hungarian algorithm
• Gale-Shapley proposal algorithm
• Tutte's matching theorem; 1-factors
• Extra Topic: Ramsey's Theorem
• Chapter 4:
• connectivity in graphs
• ear decompositions
• Menger's Theorem
• network flows; Max Flow/Min Cut
• Extra topic: matroids
• Chapter 5:
• graph coloring; color critical graphs
• 5-color Theorem for planar graphs
• Brooks's Theorem
• Turan's extremal Theorem
• the chromatic polynomial
• Extra Topic: more about Matroids
• Chapter 6:
• Euler characteristic;
• Kuratowski's Theorem