Math 381, Graph Theory
Spring 2025
Syllabus

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
  • 1.2. Subgraphs, Isomorphic Graphs, Automorphisms
    Extra: Automorphisms (handout)
  • 1.3. Trees
• Chapter 2. Colorings of Graphs
  • 2.1. Vertex Colorings
  • 2.2. Edge Colorings
    Extra: Line Graphs (handout)
  • 2.3. Decompositions and Hamilton Cycles
  • 2.4. More Decomposition
• Chapter 3. Circuits and Cycles
  • 3.1. Eulerian Circuits
• Chapter 4. Extremal Problems
  • 4.1. A Theorem of Turan
  • Extra: Line Graphs (again) (handout)
• Chapter 5. Counting
  • 5.2. Cayley's Spanning Tree Formula
    Extra: The Matrix-Tree Theorem (handout)
• Chapter 6. Labeling Graphs
  • 6.2. Conservative Graphs
• Chapter 7. Applications and Algorithms
  • 7.1. Spanning Tree Algorithms
• Chapter 8. Drawings of Graphs
  • 8.1. Planar Graphs
    Extra: The Six Color Theorem
  • 8.2. The Four Color Theorem
  • 8.3. The Five Color Theorem
• Chapter 9. Measurements of Closeness to Planarity
  • 9.1. Crossing Number