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]; [ Lecture37.pdf]; [ Lecture38.pdf]; [ Lecture39.pdf]; [ Lecture40.pdf];

- Class log

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.

Final Exam Topics: 1. Bipartite graphs. A characterization of bipartite graphs. 2. Isomorphism of graphs. 3. Representations of graphs: adjacency and incidence matrices. 4. Eulerian circuits and trails. Euler's Theorem for graphs and digraphs. 5. Graphic sequences. Havel-Hakimi Theorem on such sequences. 6. Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs. 7. Trees, characterizations of trees. Jordan's Theorem on centers of trees. 8. Counting spanning trees in graphs. Prufer codes. Matrix Tree Theorem. 9. Minimum spanning trees. Algorithms of Kruskal and Prim. 10. Matchings in bipartite graphs. Hall's Theorem. Konig-Egervary Theorem. 11. Matchings in general graphs. Tutte's 1-factor Theorem. 12. Berge-Tutte Formula and theorems of Petersen. 13. Stable matchings, Gale-Shapley Algorithm. 14. Connectivity and edge connectivity. A characterization of 2-connected graphs. Ear decomposition. Expansion Lemma. 15. Menger's Theorems, Fan Lemma. 16. Flows in networks. Decomposition of a flow into flows along cycles, t,s-paths and s,t-paths. 17. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem. 18. Integral flows (matchings in bipartite graphs, edge connectivity). 19. Planar and plane graphs. Euler's Formula. K_5 and K_{3,3} are not planar. Number of edges in planar graphs. 20. Kuratowski's Theorem and Wagner's Theorem. 21. Colorings. Greedy algorithm for coloring; d-degenerate graphs. 6-Color Theorem for planar graphs. Statement of 4-Color Theorem. 22. Properties of k-critical graphs. 23. Mycielski's Construction. Brooks' Theorem. 24. Edge colorings. Statements of Shannon's Theorem and Vizing's Theorem. Petersen Graph is not 3-edge-colorable. Edge colorings of regular simple graphs with cut edges. 25. Hamiltonian cycles in graphs. Dirac's Theorem and its sharpness examples. Tutte's example of a 3-connected 3-regular planar simple nonhamiltonian graph. 26. Extremal problems on graphs. Turan's Theorem. Ershov-Kozhuhin Theorem.

Graphs to remember: a) Complete and complete bipartite graphs, b) The k-dimensional cube Q_k, c) Petersen graph, d) de Bruijn graphs, e) A 3-regular simple graph with no perfect matchings, f) Mycielski's Graph for k=4, g) a 4-critical graph with connectivity 2, h) two n-vertex simple graphs with minimum degree (n-1)/2 and no Hamiltonian cycle, i) Shannon's Triangle, j) The Turan graph T(n,k), k) Tutte's example of a planar 3-regular 3-connected graph with no hamiltonian cycle, l) a tree and an ordering of it such that the greedy coloring of it needs 4 colors.

Hints for the exam: 1. There will be 8 problems, you need to solve all of them. Each problem costs 25 points. 2. At least one problem will be "definitions and statements of the theorems". 3. The exam will consist of two parts of 4 problems each. After you submit Part 1, you can leave the room. 4. Some problems on the final exam will be similar to problems in hw's and/or in former tests. So, understanding their solutions will be helpful. 5. Good luck!

Last changed on April 26, 2024.