Math 412
Introduction to Graph Theory
Sections X13 and X14

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: 12 Noon - 12:50 pm MWF, 245 Altgeld Hall
Final exam: 8:00-11:00 a.m., Friday, May 15.
Office hours: 2-3 pm MWF and by appointment. We use Zoom. The Zoom invitation seems to be the same as for lectures.



Class Announcements

We will have Quiz 3 on Friday, April 3 in class.

  • The next lecture invitation is: Join Zoom Meeting https://illinois.zoom.us/j/7938647305 Meeting ID: 793 864 7305
    The Zoom invitation for the 10:00am lecture seems to be the same.

  • Help sessions are on Tuesdays from 5pm to 6:30pm. The Zoom invitation seems to be the same as for the lectures.


  • Topics and proofs for Exam 2 (Spring 20)
    1. Eulerian graphs and digraphs. De Bruijn graphs. 2. Extremal problems on graphs. Mantel's Theorem. 3. Trees, characterizations of trees. 4. Prufer codes, Cayley's formula. 5. Counting spanning trees in graphs, Matrix Tree Theorem. 6. Minimum spanning trees. Algorithms of Kruskal and Prim. 7. Matchings in bipartite graphs. Hall's Theorem. 8. Matchings and covers. Konig-Egervary Theorem. 9. Gallai's Theorem ( edge covers and matchings). 10. Matchings in general graphs. Tutte's Theorem. 11. Berge-Tutte Formula, a parity remark. 12. Theorems of Petersen. 13. Connectivity and edge connectivity for graphs and directed graphs. 14. Expansion Lemma. 15. A characterization of 2-connected graphs. 16. Ear decomposition of 2-connected graphs.
    One of the problems on Exam 2 will be a proof of one of the following claims: 1. Lemma 2.7, it is in the handout [ Prim's algorithm and a lemma on minimum spanning trees] on the course page. 2. Berge's Theorem (Theorem 3.1)(Theorem 3.1.10 in the book) on M-augmenting paths. 3. Hall's Theorem (Theorem 3.2)(Theorem 3.1.11 in the book) on matchings in bipartite graphs. 4. Konig-Egervary Theorem on vertex cover in bipartite graphs (Theorem 3.4)(Theorem 3.1.16 in the book). 5. Gallai's Theorem on maximim matchings and edge covers in graphs without isolated vertices (Theorem 3.5)(Theorem 3.1.22 in the book). 6. Petersen's Theorem on 2-factors in 2k-regular graphs (Theorem 3.10) (Theorem 3.3.10 in the book). 7. Petersen's theorem (Theorem 3.9)(Corollary 3.3.8 in the book) on perfect matchings in 3-regular graphs with no cut edges.

  • 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 March 27, 2020.