#
Math 412

Introduction to Graph Theory

Sections D13 and D14

**Instructor:** Alexandr Kostochka

**Office:** 234 Illini Hall

**Phone:** (217) 265-8037 (office)

**Fax:** (217) 333-9576

**E-mail:**
kostochk@math.uiuc.edu

**Time and place:** 11 am - 11:50 am MWF, 245 Altgeld Hall

**Final exam:**
1:30-4:30 p.m., Tuesday, December 19.

**Office hours:** 3-4 pm MWF and by
appointment

##
Class Announcements

We will have Quiz 4 on Monday, November 27. Quiz 4 and Test 3 will cover
the following topics:

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. Stable matchings, Gale-Shapley algorithm.
6. Matchings in general graphs. Tutte's Theorem.
7. Berge-Tutte Formula and theorems of Petersen.
8. Connectivity and edge connectivity for graphs and directed graphs.
9. A characterization of 2-connected graphs.
10. Ear decomposition of 2-connected graphs.
11. Expansion Lemma.
12. Menger's Theorems.(!)
13. Fan Lemma.
14. Flows in networks. Decomposition of every flow into flows along cycles and
s,t-paths.
15. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.
16. Integral flows (matchings in bipartite graphs, edge connectivity).
17. Euler's Formula and its corollaries (definitions and statements).
18. Kuratowski's Theorem and Wagner's Theorem (definitions and statements).

Note that Items 17 and 18 need only definitions and statements.

We will have help sessions on Tuesdays
from 5pm to 6:30pm in 140 Burrill Hall (starting from September 5).

All exams are the evening exams in Room 112 Transportation Building from 7pm to
8:30pm on Wednesday, October 4, Wednesday, November 1 and Wednesday, November 29.

To look at your grades, go to
``www.math.uiuc.edu'', then ``courses'', then ``scores reports''.

Last changed on November 15, 2017.