#
Math 412

Introduction to Graph Theory

Sections X13 and X14

**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:** 12 Noon - 12:50 pm MWF, 245 Altgeld Hall

**Final exam:**
8:00-11:00 a.m., Friday, May 15.

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

##
Class Announcements

We will have make-up quiz on Wednesday, May 6 in class.

Topics for the quiz are:
1. Berge-Tutte Formula and theorems of Petersen.
2. Expansion Lemma, Fan Lemma.
3. Menger's Theorems.(!)
4. Flows in networks. Decomposition of every flow into flows along cycles and
s,t-paths.
5. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.
6. Integral flows (matchings in bipartite graphs, edge connectivity).
7. Plane graphs. Euler's Formula and its corollaries.
8. Outerplanar graphs, maximal planar graphs.
9. Kuratowski's Theorem and Wagner's Theorem.
10. Colorings. Greedy algorithm for coloring. A bad example for a tree.
11. Definitions and properties of d-degenerate graphs.
12. Color-critical graphs and their properties ((k-1)-edge-connected etc.).
13. Mycielski's Construction.
14. Brooks' Theorem.
15. Turan's Theorem. Ershov-Kozhuhin Theorem.
16. Edge colorings, Petersen graph is not 3-edge-colorable.
17. Shannon's Theorem and extremal examples for it.

Final Exam: 8-11 a.m., Friday, May 15.

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. 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. Connectivity and edge connectivity. A characterization of 2-connected graphs.
Ear decomposition.
14. Menger's Theorems.
15. Flows in networks. Decomposition of a flow into flows along cycles and s,t-paths.
16. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.
17. Integral flows (matchings in bipartite graphs, edge connectivity).
18. Planar and plane graphs. Euler's Formula. K_5 and K_{3,3} are not planar. Number
of edges in planar graphs.
19. Outerplanar graphs. Maximum 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. Extremal problems on graphs. Turan's Theorem. Ershov-Kozhuhin Theorem.
25. Edge colorings. Shannon's Theorem and statement of Vizing's Theorem.
Petersen Graph is not 3-edge-colorable. Edge colorings of regular simple graphs
with cut edges.
26. Hamiltonian cycles in graphs. Dirac's Theorem and its sharpness examples.

Graphs to remember:
a) Complete and complete bipartite graphs, b) The k-dimensional cube Q_k,
c) Petersen graph, d) de Bruijn graph, e) the Turan graph T(n,k),
f) Mycielski's Graph for k=4. g) Shannon's Triangle.

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

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

Last changed on May 4, 2020.