Math 412
Introduction to Graph Theory
Sections X13 and X14

Instructor: Alexandr Kostochka
Office: 255 Computer Application Building
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
E-mail: kostochk@math.uiuc.edu
Time and place: 12 Noon - 12:50 pm MWF, 108 English Building.
Final exam: 1:30-4:30 p.m., Friday, May 03.
Office hours: 2-3 pm MF and by appointment.



Class Announcements


  • We will have Quiz 4 on Monday, April 15 in class and Test 3 at 7pm on Thursday, April 18, in 160 English Building. The topics covered by Quiz 4 and Exam 3 are:
    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. Gallai's Theorem ( edge covers and matchings). 6. Stable matchings. 7. Matchings in general graphs. Tutte's Theorem. 8. Berge-Tutte Formula and theorems of Petersen. 9. Connectivity and edge connectivity. 10. A characterization of 2-connected graphs. 11. Ear decomposition of 2-connected graphs. 12. Expansion Lemma. 13. Menger's Theorems.(!) 14. Fan Lemma. 15. Flows in networks. Decomposition of every flow into flows along cycles, tis-paths and s,t-paths. 16. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem. 17. Integral flows (matchings in bipartite graphs, edge connectivity). 18. Euler's Formula and its corollaries. 19. Maximal planar graphs, outerplanar graphs. 20. Kuratowski's Theorem and Wagner's Theorem. (definitions and statements) 21. Coloring. Greedy algorithm for coloring: properties and extremal examples. 22. d-degenerate graphs: definitions and properties.
  • An example of a former Quiz 1 is here: [ A former Quiz 1.pdf];

  • The midterm tests are now planned to be evening exams in 160 English Building at 7pm on Thursdays, February 29, March 28 and April 18.
  • An example of a former Test 1 is here: [ A former Test 1.pdf];
  • Help sessions are on Tuesdays from 4pm to 5:30pm in 150 English Building.


    You may send comments to: kostochk@illinois.edu

    Last changed on April 17, 2024.