Math 412
Introduction to Graph Theory
Sections C13 and C14

Instructor: Alexandr Kostochka
Office: 234 Illini Hall
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
Time and place: 10 - 10:50 am MWF, 245 Altgeld Hall
Final exam: 7- 10 p.m., Tuesday, May 12.
Office hours: 2-3 pm MWF and by appointment. It uses Zoom. The Zoom invitation seems to be the same as for lectures.

Class Announcements

  • The next lecture invitation is: Join Zoom Meeting Meeting ID: 793 864 7305
    The Zoom invitation for the 12:00 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 ``'', then ``courses'', then ``scores reports''.

    You may send comments to:

    Last changed on March 26, 2020.