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

• random graphs
• some linear algebra
• Kastelyn's formuls for perfect matchings

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