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

Spring 2013

Room: 243 Altgeld Instructor: Derrick Stolee
Time: MWF 12:00--12:50pm Office: 226 Illini
Office Hours: T 1:00--3:00pm, R 2:00-4:00pm Email: stolee@illinois.edu
Textbook: Introduction to Graph Theory by Douglas B. West

Syllabus


Books on reserve

Exams

The midterm exams will be from 6-8pm on the following Fridays in Altgeld 145:
  • Exam 1: February 22.
  • Exam 2: March 29.
  • Exam 3: April 26.
  • Exam 4: (Make-Up) Week of April 29-31.
Exam advice

Homeworks

Advice on writing homework solutions
Homework 1Due 01/23
Homework 2Due 01/30
Homework 3Due 02/06
Homework 4Due 02/13
Homework 5Due 02/20
Homework 6Due 02/27
Homework 7Due 03/06
Homework 8Due 03/13
Homework 9Due 03/27
Homework 10Due 04/03
Homework 11Due 04/10

Collaborative Study Sessions


The collaborative study sessions are times where students can meet to discuss homework problems. Students are expected to perform serious attempts to all problems before coming to problem session. Scheduled for 5-6pm on Tuesdays, in Altgeld 145.

Topics Discussed

Below are the lecture-by-lecture topics. See this list of definitions you should know to be sure you are up-to-date on the course.
  1. 01/14 - 1.1: What is a graph? Graphs as Models.
  2. 01/16 - 1.1: More Graphs as Models. Matrices and Isomorphism. Common graphs.
  3. 01/18 - 1.1: Decompositions of Graphs, The Petersen Graph. 1.2: Strong induction, walks and paths, connected graphs.
  4. 01/23 - 1.2: Characterization of Bipartite Graphs.
  5. 01/25 - 1.2: Decomposing Complete Graphs into Bipartite Graphs, Eulerian Circuits.
  6. 01/28 - 1.3: Degree-Sum Formula, Hypercubes, Extremal results.
  7. 01/30 - 1.3: Optimization, Mantel's Theorem, Degree Sequences, Havel-Hakimi Theorem.
  8. 02/01 - 1.4: Directed graphs, Eulerian digraphs, deBruijn Cycles.
  9. 02/04 - 1.4: Tournaments and kings. 2.1: Trees, characterization of trees, spanning trees.
  10. 02/06 - 2.1: Spanning trees, distance, distance measures of trees.
  11. 02/08 - 2.2: Counting spanning trees, contractions, statement of Matrix Tree Theorem.
  12. 02/11 - 2.2: Proof of Matrix Tree Theorem. Graceful Tree Conjecture.
  13. 02/13 - 2.3: Minimum-weight spanning trees, Kruskal's algorithm, Shortest paths, Dijkstra's algorithm.
  14. 02/15 - 2.3: Proof of Dijkstra's Algorithm, Breadth-First-Search, Trees in Computer Science, Huffman's Algorithm.
  15. 02/18 - 3.1: Matchings, $M$-Augmenting Paths, Hall's Theorem, $k$-regular bipartite graphs have perfect matchings.
  16. 02/20 - 3.1: Vertex Covers, König-Egerváry Theorem, Weak/Strong Duality, Independence number, Edge-covers.
  17. 02/22 - 3.2: Augmenting Paths Algorithm, Hungarian Algorithm. Hungarian Algorithm Video, Hungarian Algorithm Example
  18. 02/25 - 3.2: Correctness of Hungarian Algorithm, Stable Matchings.
  19. 02/27 - 3.3: Factors, Tutte's Theorem, Berge-Tutte Formula.
  20. 03/01 - 3.3: Petersen's Theorem and 2-factors. 4.1: Connectivity and Edge-connectivity.
  21. 03/04 - 4.1: Connectivity, relations with edge-connectivity, bounds on edge cuts, blocks.
  22. 03/06 - 4.2: Building $k$-connected graphs from other graphs, expansion lemma, subdivisions, ear decompositions, statement of Menger's Theorem.
  23. 03/08 - 4.2: Menger's Theorem and variants, Dirac's Fan Lemma.
  24. 03/11 - 4.3: Flow problems. $f$-Aumenting Paths, Max-Flow/Min-Cut.
  25. 03/13 - 4.3: The Ford-Fulkerson Algorithm and proof of Max-Flow/Min-Cut.
  26. 03/15 - 5.1: Vertex Coloring, Lower bounds, Upper bounds using greedy algorithm, interval graphs.
  27. 03/25 - canceled
  28. 03/27 - 5.1: More greedy coloring bounds, Brooks' Theorem.
  29. 03/29 - 5.2: Graphs with high chromatic number and low clique number, Turan's Theorem.
  30. 04/01 - 5.2: Connectivity of $k$-critical graphs.
  31. 04/03 - 6.1: Planar graphs and planar embeddings. Definition of outerplanar.
  32. 04/05 - 6.1: More on planarity.