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, 245 Altgeld Hall
Final exam:
1:30-4:30 p.m., Friday, May 12.
Office hours: Temporarily, 2-3 pm MF and by
appointment.
Class Announcements
An example of a former Test 1 is here: [ A former Test 1.pdf];
As a preparation for Test 2, we have Quiz 3 on Friday, March 10 in class. It will cover the same topics as Test 2 (see below).
We have Test 2 on Wednesday, March 22 from 7pm to 8:30pm in 1024 Chemistry Annex.
It will cover the following topics:
1. Eulerian graphs and digraphs. De Bruijn graphs.
2. Extremal problems on graphs. Mantel's Theorem.
3. Trees, characterizations of trees.
4. Prufer codes, Cayley's formula.
5. Counting spanning trees in graphs, Matrix Tree Theorem.
6. Minimum spanning trees. Algorithms of Kruskal and Prim.
7. Matchings in bipartite graphs. Hall's Theorem.
8. Matchings and covers. Konig-Egervary Theorem.
9. Gallai's Theorem (edge covers and matchings).
10. Matchings in general graphs. Tutte's Theorem.
11. Berge-Tutte Formula, a parity remark.
12. Theorems of Petersen.
13. Connectivity and edge connectivity for graphs and directed graphs.
14. Expansion Lemma.
15. A characterization of 2-connected graphs.
One of the problems on Test 2 will be a proof of one of the following claims:
1. Jordan's Theorem on centers of trees.
2. Hall's Theorem on matchings.
3. Konig-Egervary Theorem on matchings.
4. First Theorem of Petersen (on 3-regular graphs).
5. Second Theorem of Petersen (on 2k-regular graphs).
6. Expansion Lemma.
7. Whitney's Theorem on 2-connected graphs.
We have the final exam at 1:30-4:30 p.m. on Friday, May 12 in our class room.
Help sessions are on Tuesdays from 4pm to 5:30pm in Room 243 Altgeld Hall.
Last changed on March 29, 2023.