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.

Current homework
[hw9.pdf];
Past homework
[hw1.pdf]; [hw2.pdf]; [hw3.pdf]; [hw4.pdf]; [hw5.pdf]; [hw6.pdf]; [hw7.pdf]; [hw8.pdf];
Class info [ Class info], [ Safety info], [ Gale-Shapley paper ], [ Edmonds' paper ],
Lecture slides
[ Lecture1.pdf]; [ Lecture2.pdf]; [ Lecture3.pdf]; [ Lecture4.pdf]; [ Lecture5.pdf]; [ Lecture6.pdf]; [ Lecture7.pdf]; [ Lecture8.pdf]; [ Lecture9.pdf]; [ Lecture10.pdf]; [ Lecture11.pdf]; [ Lecture12.pdf]; [ Lecture13.pdf]; [ Lecture14.pdf]; [ Lecture15.pdf]; [ Lecture16.pdf]; [ Lecture17.pdf]; [ Lecture18.pdf]; [ Lecture19.pdf]; [ Lecture20.pdf]; [ Lecture21.pdf]; [ Lecture22.pdf]; [ Lecture23.pdf]; [ Lecture24.pdf]; [ Lecture25.pdf]; [ Lecture26.pdf]; [ Lecture27.pdf]; [ Lecture28.pdf]; [ Lecture29.pdf]; [ Lecture30.pdf]; [ Lecture31.pdf]; [ Lecture32.pdf]; [ Lecture33.pdf]; [ Lecture34.pdf]; [ Lecture35.pdf]; [ Lecture36.pdf];
Class log

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.

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.

Math 412 Introduction to Graph Theory Sections C13 and C14

Class Announcements

You may send comments to: kostochk@illinois.edu Last changed on April 19, 2024.

Math 412
Introduction to Graph Theory
Sections C13 and C14

You may send comments to: kostochk@illinois.edu

Last changed on April 19, 2024.