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
Time and place: 12 Noon - 12:50 pm MWF, 141 Loomis Laboratory
Final exam: 7:00-10:00 p.m., Thursday, May 13.
Office hours: 2-3 pm MF and by appointment. We use Zoom.

Class Announcements

  • Final Exam Topics: 1. Bipartite graphs. A characterization of bipartite graphs. 2. Isomorphism of graphs. 3. Representations of graphs: adjacency and incidence matrices. 4. Eulerian circuits and trails. Euler's Theorem for graphs and digraphs. 5. Graphic sequences. Havel-Hakimi Theorem on such sequences. 6. Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs. 7. Trees, characterizations of trees. Centers of trees. 8. Counting spanning trees in graphs. Prufer codes. Matrix Tree Theorem. 9. Minimum spanning trees. Algorithms of Kruskal and Prim. 10. Matchings in bipartite graphs. Hall's Theorem. Konig-Egervary Theorem. 11. Matchings in general graphs. Tutte's 1-factor Theorem. 12. Berge-Tutte Formula and theorems of Petersen. 13. Stable matchings, Gale-Shapley Algorithm. 14. Connectivity and edge connectivity. A characterization of 2-connected graphs. Ear decomposition. Expansion Lemma. 15. Menger's Theorems, Fan Lemma. 16. Flows in networks. Decomposition of a flow into flows along cycles and s,t-paths. 17. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem. 18. Integral flows (matchings in bipartite graphs, edge connectivity). 19. Planar and plane graphs. Euler's Formula. K_5 and K_{3,3} are not planar. Number of edges in planar graphs. 20. Kuratowski's Theorem and Wagner's Theorem. 21. Colorings. Greedy algorithm for coloring; d-degenerate graphs. 6-Color Theorem for planar graphs. Statement of 4-Color Theorem. 22. Properties of k-critical graphs. 23. Mycielski's Construction. Brooks' Theorem. 24. Edge colorings. Statements of Shannon's Theorem and Vizing's Theorem. Petersen Graph is not 3-edge-colorable. Edge colorings of regular simple graphs with cut edges.
    Graphs to remember: a) Complete and complete bipartite graphs, b) The k-dimensional cube Q_k, c) Petersen graph, d) de Bruijn graph, e) A 3-regular simple graph with no perfect matchings, f) Mycielski's Graph for k=4, g) a k-wheel, h) A 4-critical graph with connectivity 2.

  • Final Exam: 7:00-10:00 p.m., Thursday, May 13.

  • Help sessions are on Tuesdays from 4pm to 5:30pm in Room 1060 Lincoln Hall.

    You may send comments to:

    Last changed on May 4, 2021.