#
Math 412

Introduction to Graph Theory

Sections C13 and C14

**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:** 10 - 10:50 am MWF, 245 Altgeld Hall

**Final exam:**
7- 10 p.m., Tuesday, May 12.

**Office hours:** 2-3 pm MWF and by
appointment. It uses Zoom. The Zoom invitation seems to be the same as for lectures.

##
Class Announcements

The next lecture invitation is: Join Zoom Meeting
https://illinois.zoom.us/j/7938647305
Meeting ID: 793 864 7305

The Zoom invitation for the 12:00 lecture seems to be the same.

Help sessions are on Tuesdays from 5pm to 6:30pm.
The Zoom invitation seems to be the same as for the lectures.

Topics and proofs for Exam 2 (Spring 20)

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.
16. Ear decomposition of 2-connected graphs.

One of the problems on Exam 2 will be a proof of one of the following claims:
1. Lemma 2.7, it is in the handout [ Prim's algorithm and a lemma on minimum
spanning trees] on the course page.
2. Berge's Theorem (Theorem 3.1)(Theorem 3.1.10 in the book) on M-augmenting paths.
3. Hall's Theorem (Theorem 3.2)(Theorem 3.1.11 in the book) on matchings
in bipartite graphs.
4. Konig-Egervary Theorem on vertex cover in bipartite graphs (Theorem 3.4)(Theorem
3.1.16 in the book).
5. Gallai's Theorem on maximim matchings and edge covers in graphs without isolated
vertices (Theorem 3.5)(Theorem 3.1.22 in the book).
6. Petersen's Theorem on 2-factors in 2k-regular graphs (Theorem 3.10) (Theorem 3.3.10 in the book).
7. Petersen's theorem (Theorem 3.9)(Corollary 3.3.8 in the book) on perfect matchings
in 3-regular graphs with no cut edges.

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

Last changed on March 26, 2020.