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
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

  • The final exam will cover the following 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. Extremal problems on graphs. Mantel's Theorem. 6. Graphic sequences. Havel-Hakimi Theorem on such sequences. 7. Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs. 8. Tournaments, kings in tournaments. 9. Trees, characterizations of trees. Centers of trees. 10. Counting spanning trees in graphs. Prufer codes. Matrix Tree Theorem. 11. Minimum spanning trees. Algorithms of Kruskal and Prim. 12. Matchings in bipartite graphs. Hall's Theorem. 13. Matchings and covers. Konig-Egervary Theorem. 14. Stable matchings. 15. Matchings in general graphs. Tutte's 1-factor Theorem. 16. Berge-Tutte Formula and theorems of Petersen. 17. Connectivity and edge connectivity. A characterization of 2-connected graphs. 18. Ear decomposition. 19. Menger's Theorems. 20. Flows in networks. Decomposition of a flow into flows along cycles and s,t-paths. 21. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem. 22. Integral flows (matchings in bipartite graphs, edge connectivity). 23. Planar and plane graphs. 24. Euler's Formula. K_5 and K_{3,3} are not planar. Number of edges in planar graphs. 25. Outerplanar graphs. Triangulations. 26. Kuratowski's Theorem and Wagner's Theorem. 27. Colorings. Greedy algorithm for coloring; d-degenerate graphs. 28. Properties of k-critical graphs. 29. Mycielski's Construction. Brooks' Theorem. 30. 6-Color Theorem for planar graphs. Statement of 4-Color Theorem. 31. Extremal problems on graphs. Turan's Theorem. Ershov-Kozhuhin Theorem. 32. Edge colorings. Shannon's Theorem and statement of Vizing's Theorem. Petersen Graph is not 3-edge-colorable. Edge colorings of regular simple graphs with cut edges. 33. Hamiltonian cycles in graphs. Dirac's Theorem and its sharpness examples. Tutte's example of a 3-connected 3-regular planar simple nonhamiltonian graph.
    Graphs to remember: a) Complete and complete bipartite graphs, b) The k-dimensional cube Q_k, c) Petersen graph, d) de Bruijn graph, e) the Turan graph T(n,k), f) Mycielski's Graph for k=4. g) Shannon's Triangle.

    Comment: Among items 31-33, you need to be able to prove only Ershov-Kozhuhin Theorem and Shannon's Theorem.
  • We will have a help session for the final on December 18 from Noon to 1 pm in our classroom. You also may visit the help session for the other class on December 18 from Noon to 1 pm in 245 Altgeld Hall.

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

    You may send comments to:

    Last changed on December 12, 2017.