#
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 am MWF, 245 Altgeld Hall

**Final exam:**
1:30-4:30 p.m., Friday, December 14.

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

##
Class Announcements

We will have Test 3 on Wednesday, December 5 at 7pm in 245 Altgeld.
Topics for Test 3 are:
1. Extremal problems on graphs. Mantel's Theorem.
2. Counting spanning trees in graphs.
3. Matchings in bipartite graphs. Hall's Theorem.
4. Matchings and covers. Konig-Egervary Theorem.
5. Gallai's Theorem ( edge covers and matchings).
6. Stable matchings.
7. Matchings in general graphs. Tutte's Theorem.
8. Berge-Tutte Formula and theorems of Petersen.
9. Connectivity and edge connectivity.
10. A characterization of 2-connected graphs.
11. Ear decomposition of 2-connected graphs.
12. Expansion Lemma.
13. Menger's Theorems.(!)
14. Fan Lemma.
15. Flows in networks. Decomposition of every 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. Euler's Formula and its corollaries.
19. Maximal planar graphs, outerplanar graphs.
20. Kuratowski's Theorem and Wagner's Theorem. (definitions and statements)
21. Colorings. Greedy algorithm for coloring; d-degenerate graphs.
22. Properties of k-critical graphs.
23. 6-Color Theorem for planar graphs. Statement of 4-Color Theorem.

We will have the make-up Quiz 5 on Monday, December 10. Topics for Quiz 5 are:
1. Matchings in bipartite graphs. Hall's Theorem.
2. Matchings and covers. Konig-Egervary Theorem.
3. Matchings in general graphs. Tutte's Theorem.
4. Berge-Tutte Formula and theorems of Petersen.
5. Matrix Tree Theorem.
6. A characterization of 2-connected graphs.
7. Expansion Lemma, Fan Lemma.
8. Menger's Theorems.(!)
9. Flows in networks. Decomposition of every flow into flows along cycles and
s,t-paths.
10. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.
11. Integral flows (matchings in bipartite graphs, edge connectivity).
12. Planar and plane graphs. Dual graphs.
13. Euler's Formula and its corollaries.
14. Outerplanar graphs, maximal planar graphs.
15. Kuratowski's Theorem and Wagner's Theorem.
16. Colorings. Greedy algorithm for coloring. A bad example for a tree.
17. Color-critical graphs and their properties ((k-1)-edge-connected etc.).
18. Brooks' Theorem.
19. Turan'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. Extremal problems on graphs. Mantel's Theorem.
6. Graphic sequences. Havel-Hakimi Theorem on such sequences.
7. Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs.
8. Tournaments, kings in tournaments.
9. Trees, characterizations of trees. Centers of trees.
10. Counting spanning trees in graphs. Prufer codes. Matrix Tree Theorem.
11. Minimum spanning trees. Algorithms of Kruskal and Prim.
12. Matchings in bipartite graphs. Hall's Theorem.
13. Matchings and covers. Konig-Egervary Theorem.
14. Stable matchings.
15. Matchings in general graphs. Tutte's 1-factor Theorem.
16. Berge-Tutte Formula and theorems of Petersen.
17. Connectivity and edge connectivity. A characterization of 2-connected graphs.
18. Ear decomposition.
19. Menger's Theorems.
20. Flows in networks. Decomposition of a flow into flows along cycles and s,t-paths.
21. Ford-Fulkerson Algorithm. Max Flow--Min Cut Theorem.
22. Integral flows (matchings in bipartite graphs, edge connectivity).
23. Planar and plane graphs.
24. Euler's Formula. K_5 and K_{3,3} are not planar. Number of edges in planar graphs.
25. Outerplanar graphs. Triangulations.
26. Kuratowski's Theorem and Wagner's Theorem.
27. Colorings. Greedy algorithm for coloring; d-degenerate graphs.
28. Properties of k-critical graphs.
29. Mycielski's Construction. Brooks' Theorem.
30. 6-Color Theorem for planar graphs. Statement of 4-Color Theorem.
31. Extremal problems on graphs. Turan's Theorem. Ershov-Kozhuhin Theorem.
32. 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.
33. Hamiltonian cycles in graphs. Dirac's Theorem and its sharpness examples.
Tutte's example of a 3-connected 3-regular planar simple nonhamiltonian graph.

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.

One of the problems on the final will be a proof of one of the following 7 theorems:
1. Konig's Theorem on bipartite graphs (Theorem 1.2.8 in the book),
2. Mantel's Theorem on the number of edges in triangle-free graphs(Theorem 1.2.8 in the book),
3. Theorem on the existence of kings in a tournament (Prop. 1.4.30 in the book),
4. Gallai's Theorem edge cover number versus matching number (Theorem 3.1.22 in the book),
5. Berge's Theorem on M-augmenting paths (Theorem 3.1.10 in the book),
6. Petersen's Theorem on 2-factors in 2k-regular graphs (Cor. 3.3.10 in the book),
7. Whitney's Theorem on internally disjoint paths in 2-connected graphs (Theorem 4.2.2 in the book).

We will have help sessions for the final on December 13 and 14
from Noon to 1 pm in our classroom.

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

Last changed on December 06, 2018.