Math 412
Introduction to Graph Theory
Sections X13 and X14
Instructor: Alexandr Kostochka
Office: 255 Computer Application Building
Phone: (217) 265-8037 (office)
Fax: (217) 333-9576
E-mail:
kostochk@math.uiuc.edu
Time and place: 12 Noon - 12:50 pm MWF, 108 English Building.
Final exam:
1:30-4:30 p.m., Friday, May 03.
Office hours: 2-3 pm MF and by
appointment.
Class Announcements
We will have Quiz 4 on Monday, April 15 in class and Test 3 at 7pm
on Thursday, April 18, in 160 English Building. The topics covered by
Quiz 4 and Exam 3 are:
1. Extremal problems on graphs. Mantel's Theorem.
2. Counting spanning trees in graphs: Prufer codes and Matrix Tree Theorem.
3. Matchings in bipartite graphs. Hall's Theorem.
4. Matchings and covers. Konig-Egervary Theorem.
5. Gallai's Theorem ( edge covers and matchings).
6. Stable matchings.
7. Matchings in general graphs. Tutte's Theorem.
8. Berge-Tutte Formula and theorems of Petersen.
9. Connectivity and edge connectivity.
10. A characterization of 2-connected graphs.
11. Ear decomposition of 2-connected graphs.
12. Expansion Lemma.
13. Menger's Theorems.(!)
14. Fan Lemma.
15. Flows in networks. Decomposition of every flow into flows along cycles, tis-paths and
s,t-paths.
16. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.
17. Integral flows (matchings in bipartite graphs, edge connectivity).
18. Euler's Formula and its corollaries.
19. Maximal planar graphs, outerplanar graphs.
20. Kuratowski's Theorem and Wagner's Theorem. (definitions and statements)
21. Coloring. Greedy algorithm for coloring: properties and extremal examples.
22. d-degenerate graphs: definitions and properties.
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
Thursdays, February 29, March 28 and April 18.
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 150 English Building.
Last changed on April 17, 2024.