Math 381, Graph Theory
Spring 2021
Syllabus with Recordings

Textbook

Nora Hartsfield and Gerhard Ringel, Pearls in Graph Theory, third edition (Dover, 2003).
(Essentially the same as the second edition, Academic Press, 1994.)

Topics

• Chapter 1. Basic Graph Theory
  • 1.1. Graphs and Degrees of Vertices
    • Thurs. 2/11: Recording
    • Fri. 2/12: Recording
    • Mon. 2/15: Recording
    • Wed. 2/17: Recording
  • 1.2. Subgraphs, Isomorphic Graphs, Automorphisms
    • Thurs. 2/18: Recording
    • Extra: Automorphisms (handout)
  • 1.3. Trees
    • Fri. 2/19: Recording
    • Mon. 2/22: Recording
• Chapter 2. Colorings of Graphs
  • 2.1. Vertex Colorings
    • Wed. 2/24: Recording
    • Thurs. 2/25: Recording
    • Fri. 2/26: Recording
    • Mon. 3/1: Recording
    • Wed. 3/3: Recording
    • Thurs. 3/4: Recording of summary (I forgot to record the class)
    • Fri. 3/5: Recording
    • Extra: Chromatic Polynomial (handout)
  • 2.2. Edge Colorings
    • Mon. 3/8: Recording of summary (I forgot to record the class)
    • Extra: Line Graphs (handout)
  • 2.3. Decompositions and Hamilton Cycles
    • Wed. 3/10: Recording
  • 2.4. More Decomposition
    • Thurs. 3/11: Recording
    • Fri. 3/12: Recording
• Chapter 3. Circuits and Cycles
  • 3.1. Eulerian Circuits
    • Mon. 3/15: Recording
    • Thurs. 3/18: Recording
  • Review
    • Fri. 3/19: Recording
  • 3.2. The Oberwohlfach Problem
    • Thurs. 3/25: Recording (also Turan's Theorem)
• Chapter 4. Extremal Problems
  • 4.1. A Theorem of Turan
    • Mon. 3/22: Recording
    • Wed. 3/24: Recording (homework discussion)
  • 4.2. Cages
    • Fri. 3/26: Recording
  • Extra: Line Graphs (again) (handout)
• Chapter 5. Counting
  • 5.1. Counting 1-Factors
    • Mon. 3/29: Recording
  • 5.2. Cayley's Spanning Tree Formula
    • Wed. 3/31: Recording
    • Thurs. 4/1: Recording
    • Fri. 4/2: Recording (HW V review)
  • Extra: The Matrix-Tree Theorem (handout)
    • Mon. 4/5:
    • Wed. 4/7: Recording with HW VI discussion
    • Fri. 4/9: Recording
  • 5.3. More Spanning Trees
    • Mon. 4/12: Recording
• Linear algebra bonus: Graphs as Arrangements of Lines, Planes, or Hyperplanes (will not be tested)
  • Wed. 4/14: Recording
• Chapter 6. Labeling Graphs
  • 6.1. Magic Graphs and Graceful Trees
    • Thurs. 4/15: Recording
  • 6.2. Conservative Graphs
    • Fri. 4/16: Recording
• Chapter 7. Applications and Algorithms
  • 7.1. Spanning Tree Algorithms
    • Mon. 4/19: Recording (also with conservative graphs)
    • Wed. 4/21: Recording (also with conservative graphs and homework)
• Chapter 8. Drawings of Graphs
  • 8.1. Planar Graphs
    • Thurs. 4/22: Recording (and homework questions)
    • Fri. 4/23: Recording
    • Mon. 4/26: Recording (including 5-Color Theorem for graphs)
  • 8.3. The Five Color Theorem
    • Wed. 4/28: Recording (including duality and 4-Color related topics)
  • 8.2. The Four Color Theorem
    • Thurs. 4/29: Recording (with crossing number)
• Chapter 9. Measurements of Closeness to Planarity
  • 9.1. Crossing Number
    • Fri. 4/30: Recording (including use of Kuratowski's Theorem, and homework)
    • Mon. 5/3: Recording (vocal only; the class begins at 31 minutes into the recording)
  • 9.2. Thickness and Splitting Number
    • Wed. 5/5: Recording (with HW X problem discussion)
    • Thurs. 5/6: Recording (with HW XI problem discussion)
  • 9.3. Heawood's Empire Problem
    • Fri. 5/7: Recording (and Homework XI discussion)
    • Mon. 5/10: Recording (and higher surfaces for Ch. 10)
• Chapter 10 and Extra. Graphs on Other Surfaces
  • Diagrams for the Torus, Double Torus, etc. (in class)
    • Wed. 5/12: Recording
    • Thurs. 5/13: Recording
  • 10.3. The Genus of a Graph
    (Omit anything about "schemes", "maximal rotations", and "current graphs", and pp. 235-237.)
    • Fri. 5/14: Recording
    • Mon. 5/17: Recording (homework and Petersen graph)