Math 412
Introduction to Graph Theory
Sections E13 and E14

Instructor: Alexandr Kostochka
Office: 234 Illini Hall
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
E-mail: kostochk@math.uiuc.edu
Time and place: 1pm - 1:50 pm MWF, 156 Henry Administration Bldg.
Final exam: 8:00-11:00 a.m., Wednesday, December 20.
Office hours: 3-4 pm MWF and by appointment



Class Announcements

  • We will have Quiz 4 on Monday, November 27. Quiz 4 and Test 3 will cover the following topics:
    1. Extremal problems on graphs. Mantel's Theorem. 2. Counting spanning trees in graphs: Prufer codes and Matrix Tree Theorem. 3. Matchings in bipartite graphs. Hall's Theorem. 4. Matchings and covers. Konig-Egervary Theorem. 5. Stable matchings, Gale-Shapley algorithm. 6. Matchings in general graphs. Tutte's Theorem. 7. Berge-Tutte Formula and theorems of Petersen. 8. Connectivity and edge connectivity for graphs and directed graphs. 9. A characterization of 2-connected graphs. 10. Ear decomposition of 2-connected graphs. 11. Expansion Lemma. 12. Menger's Theorems.(!) 13. Fan Lemma. 14. Flows in networks. Decomposition of every flow into flows along cycles and s,t-paths. 15. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem. 16. Integral flows (matchings in bipartite graphs, edge connectivity). 17. Euler's Formula and its corollaries (definitions and statements). 18. Kuratowski's Theorem and Wagner's Theorem (definitions and statements).
    Note that Items 17 and 18 need only definitions and statements.


  • We will have help sessions on Tuesdays from 5pm to 6:30pm in 140 Burrill Hall (starting from September 5).

  • All exams are the evening exams in Room 112 Transportation Building from 7pm to 8:30pm on Thursday, October 5, Thursday, November 2 and Thursday, November 30.

  • To look at your grades, go to ``www.math.uiuc.edu'', then ``courses'', then ``scores reports''.


    You may send comments to: kostochk@math.uiuc.edu

    Last changed on November 15, 2017.