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.

- Current homework

[hw7.pdf]; [hw8.pdf];

- Past homework

[hw1.pdf]; [hw2.pdf]; [hw3.pdf]; [hw4.pdf]; [hw5.pdf]; [hw6.pdf]; - Class info [ Class info], [ Safety info],
- 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];

- Class log

An example of a former Test 1 is here: [ A former Test 1.pdf];

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.

Last changed on March 29, 2023.