# Math 412 Introduction to Graph Theory Sections C13 and C14

Instructor: Alexandr Kostochka
Office: 255 Computer Application Building
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
E-mail: kostochk@illinois.edu
Time and place: 10 - 10:50 am MWF, 1027 Lincoln Hall.
Final exam: 1:30-4:30 p.m., Friday, May 10.
Office hours: Temporarily, 2-3 pm MF and by appointment.

## Class Announcements

• We will have the Make-Up Quiz on Friday, April 26 in class. The topics covered by the Quiz are:
1. Matchings and covers. Konig-Egervary Theorem. Gallai's Theorem. 2. Matchings in general graphs. Tutte's Theorem, Berge-Tutte Formula. 3. Planar and plane graphs. Euler's Formula and its corollaries. 4. Outerplanar graphs, maximal planar graphs. 5. Kuratowski's Theorem and Wagner's Theorem. 6. Colorings. Greedy algorithm for coloring. A bad example for a tree. 7. d-Degenerate graphs and their definitions. 8. Color-critical graphs and their properties ((k-1)-edge-connected etc.). 9. Mycielski's Construction. 10. Brooks' Theorem. 11. Edge colorings, Properties of edge colorings. Petersen graph is not 3-edge-colorable. 12. Shannon's Theorem and extremal examples for it. Vizing's Theorem.
• Below please find the list of topics for the final, the list of graphs you need to remember and some hints for the final. Proofs of the theorems learned in class will not be needed, but you would need to remember the statements and apply them.
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. Jordan's Theorem on 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, t,s-paths 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. 25. Hamiltonian cycles in graphs. Dirac's Theorem and its sharpness examples. Tutte's example of a 3-connected 3-regular planar simple nonhamiltonian graph. 26. Extremal problems on graphs. Turan's Theorem. Ershov-Kozhuhin Theorem.
Graphs to remember: a) Complete and complete bipartite graphs, b) The k-dimensional cube Q_k, c) Petersen graph, d) de Bruijn graphs, e) A 3-regular simple graph with no perfect matchings, f) Mycielski's Graph for k=4, g) a 4-critical graph with connectivity 2, h) two n-vertex simple graphs with minimum degree (n-1)/2 and no Hamiltonian cycle, i) Shannon's Triangle, j) The Turan graph T(n,k), k) Tutte's example of a planar 3-regular 3-connected graph with no hamiltonian cycle, l) a tree and an ordering of it such that the greedy coloring of it needs 4 colors.
Hints for the exam: 1. There will be 8 problems, you need to solve all of them. Each problem costs 25 points. 2. At least one problem will be "definitions and statements of the theorems". 3. The exam will consist of two parts of 4 problems each. After you submit Part 1, you can leave the room. 4. Some problems on the final exam will be similar to problems in hw's and/or in former tests. So, understanding their solutions will be helpful. 5. Good luck!
• NO class on Monday, April 29. NO help session on Tuesday, April 30. An extra office hour on Wednesday, May 1 at 1:30pm. An extra help session on Thursday, May 9 at Noon.
• 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 Wednesdays, February 28, March 27 and April 17.
• 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 Room 150 English Building.