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, 165 Noyes Laboratory.
Final exam: 1090 Lincoln Hall,
1:30-4:30 p.m., Thursday, May 15.
Office hours: 2-3 pm MF and by
appointment.
Class Announcements
We will have an extra help session on Wednesday, May 14 at Noon in our classroom.
Topics for Quiz 5 are:
1. Matchings and covers. Konig-Egervary Theorem. Gallai's Theorem.
2. Matchings in general graphs. Tutte's Theorem, Berge-Tutte Formula.
3. Connectivity and edge connectivity, Expansion Lemma.
4. Flows in networks, Ford-Fulkerson Algorithm, MaxFlow-MinCut Theorem.
5. Planar and plane graphs. Euler's Formula and its corollaries.
6. Kuratowski's Theorem and Wagner's Theorem.
7. Colorings. Greedy algorithm for coloring. A bad example for a tree.
8. d-Degenerate graphs, their definitions and applications.
9. Color-critical graphs and their properties ((k-1)-edge-connected etc.).
10. Mycielski's Construction and Brooks' Theorem.
11. Edge colorings, Petersen graph is not 3-edge-colorable.
12. Shannon's Theorem and extremal examples for it.
13. Vizing's Theorem and Tait's Theorem.
14. Dirac's Theorem on hamiltonian cycles, extremal examples for it.
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. The ideas of the proofs may be needed to solve the problems in the test.
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, matchings in bipartite graphs.
18. Planar and plane graphs. Euler's Formula. K_5 and K_{3,3} are not planar. Number of edges in planar simple graphs.
19. Kuratowski's Theorem and Wagner's Theorem.
20. Colorings. Greedy algorithm for coloring; d-degenerate graphs. 6-Color Theorem for planar graphs.
21. Properties of k-critical graphs.
22. Mycielski's Construction. Brooks' Theorem.
23. 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.
24. Hamiltonian cycles in graphs. Dirac's Theorem and its sharpness examples. Tutte's example of a 3-connected 3-regular planar simple nonhamiltonian graph.
25. Extremal problems on graphs. Turan's Theorem. Ershov-Kozhuhin Theorem.
Graphs to remember:
a) Complete and complete bipartite graphs, b) Petersen graph, c) de Bruijn graphs, d) A 3-regular simple graph with no perfect matchings, e) Mycielski's Graph for k=4, f) a 4-critical graph with connectivity 2, g) two n-vertex simple graphs with minimum degree (n-1)/2 and no Hamiltonian cycle, h) Shannon's Triangle, i) The Turan graph T(n,k), j) Tutte's example of a planar 3-regular 3-connected graph with no hamiltonian cycle,
k) 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 two sets of 4 problems each. 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!
The tests are planned to be evening exams in 120 Architecture Building
at 7pm on
Wednesdays, February 26, April 2 and April 23.
An example of a former Test 1 is here: [ A former Test 1.pdf];
Currently our four quizzes are planned to be in class on Friday February 7, Monday February 24, Friday March 28 and Monday April 21.
An example of a former Quiz 1 is here: [ A former Quiz 1.pdf];
Help sessions are on Tuesdays from 4pm to 5:30pm in Room 1028 Lincoln Hall.
Last changed on May 05, 2025.