Derrick Stolee
J. L. Doob Research Assistant Professor
Department of Mathematics
University of Illinois at Urbana-Champaign

Home

Teaching

Papers

Presentations

Software

Other

MATH 412 - Graph Theory

Fall 2012

Room: 341 Altgeld Instructor: Derrick Stolee
Time: MWF 12:00--12:50pm Office: 226 Illini
Office Hours: MW 2:00--3:30pm Email: stolee@illinois.edu
Textbook: Introduction to Graph Theory by Douglas B. West

Syllabus


Books on reserve

Exams

The midterm exams will be on Mondays from 7-9 in Altgeld 145 (same as the problem sessions). On exam weeks, the problem sessions will be on Tuesdays, 5-7 (Altgeld 145).
  • Exam 1: September 17th. Covers all of Chapter 1.
  • Exam 2: October 15th. Covers Chapters 2, 3, and Section 4.1.
  • Exam 3: November 12th. covers Chapters 4 and 5.
  • Exam 4: (Optional) December 10th. Comprehensive.
Exam advice

Homeworks

Homework 1Due 09/05
Homework 2Due 09/12
Homework 3Due 09/19
Homework 4Due 09/26
Homework 5Due 10/03
Homework 6Due 10/10
Homework 7Due 10/17
Homework 8Due 10/24
Homework 9Due 10/31
Homework 10Due 11/7
Homework 11Due 11/14
Homework 12Due 11/28
Homework 13Due 12/05
Homework 14Due 12/12

Collaborative Study Sessions

Non-Exam Weeks: Monday 7-9pm, Altgeld 145.
Exam Weeks: Tuesday 5-7pm, Altgeld 145.

Advice on writing homework solutions

Topics Discussed

  1. 08/27 - 1.1: What is a graph? Graphs as Models.
  2. 08/29 - 1.1: Graphs as Models, Matrices and Isomorphism.
  3. 08/31 - 1.1: Matrices and Isomorphism, Decomposition and Special Graphs. 1.2: Paths, Cycles, and Trails.
  4. 09/05 - 1.2: Connectivity and Bipartite Graphs
  5. 09/07 - 1.2: Eulerian Circuits. 1.3: Degree sum formula
  6. 09/10 - 1.3: Counting and Bijctions, Extremal and Optimization problems, Mantel's Theorem.
  7. 09/12 - 1.3: Graphic degree sequences, Havel-Hakimi Theorem. 1.4: Directed graphs.
  8. 09/14 - 1.4: Directed degrees, de Bruijn Cycles, Tournaments.
  9. 09/17 - 2.1: Characterization of Trees, Spanning Trees.
  10. 09/19 - 2.1: Distance, diameter, radius. Paths and Stars are extremal. 2.2: Cayley's Formula.
  11. 09/21 - 2.2: Matrix-Tree Theorem, Graceful Labelings.
  12. 09/24 - 2.2: More on Graceful Labelings, 2.3: Kruskal's Algorithm.
  13. 09/26 - 2.3: Dijkstra's Algorithm, Breadth-First Search, Chinese Postman Problem.
  14. 09/28 - 3.1: Hall's Theorem, König-Egerváry Theorem, Weak and Strong Duality.
  15. 10/01 - 3.1: Independence number and edge covers. 3.3: Tutte's Contition and Theorem.
  16. 10/03 - 3.3: Tutte's Theorem (continued). Berge-Tutte Formula, Petersen's Theorem.
  17. 10/05 - 3.2: Augmenting Path Algorithms, Weighted Matchings/Covers, Hungarian Algorithm.
  18. 10/08 - 3.2: Correctness of Hungarian Algorithm, Stable Matchings, 3.3: Petersen's Corollary.
  19. 10/10 - 3.3: 2-factors in Regular graphs. 4.1: Definitions of connectivity.
  20. 10/12 - 4.1: Examples of connectivity. Edge-connectivity. Blocks.
  21. 10/15 - 4.1: Properties of Blocks, 4.2: Structure of 2-connected graphs.
  22. 10/17 - 4.2: Structure of k-connected graphs, internally-disjoint paths, Menger's Theorem and variants.
  23. 10/22 - 4.2: Proof of Menger's Theorem and Corollaries.
  24. 10/24 - 4.3: Network flows, f-augmenting paths, source/sink cuts.
  25. 10/26 - 4.3: Ford-Fulkerson Algorithm, Max-Flow/Min-Cut.
  26. 10/29 - 4.3: Applications of Integral Max-Flow/Min-Cut. 5.1: Vertex Coloring, Lower Bounds.
  27. 10/31 - 5.1: Upper bounds using greedy coloring. Interval Graphs. Gallai-Roy-Vitaver Theorem.
  28. 11/01 - 5.1: Proof of Gallai-Roy-Vitaver, Brooks' Theorem, Mycielski's Construction.
  29. 11/07 - 5.2: Properties of Mycielski's Construction, Turán's Theorem.
  30. 11/09 - 5.2: Structure of k-critical graphs.
  31. 11/13 - 6.1: Planar Embeddings, Dual Graphs.
  32. 11/15 - 6.1: Outerplanar Graphs, Euler's Formula.
  33. 11/17 - 6.2: Kuratowski's Theorem.
  34. 11/26 - 6.3: The 6-, 5-, and 4-Color Theorems, Kempe Chains.
  35. 11/28 - 6.3: Thickness, Crossing Number, Guy's Theorem.