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
grading: Your grade is based on 4 components:
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.
Click here for the assignments.
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