Graph Theory

Preliminary exam program

1. Graph, directed graph. Vertices, edges, degrees of vertices. Sum of degrees.
2. Equivalence relation and equivalence classes, Connected components of graphs and strong connected components of directed graphs.
3. Trees. Several definitions. Spanning tree.
4. Matrix Tree theorem. Caley theorem on labeled trees enumeration.
5. Two-connectivity. Block structure of the graph.
6. Connectivity: Hoering and Menger theorems.
7. Matchings in bipartite graphs. Hall (marriages) theorem. Generalized Hall theorem, Koenig theorem.
8. Dilworth theorem.
9. Matchings in non-bipartite graphs. Tutte theorem, Berges formula.
10. Euler paths and Euler cycles. Criteria in terms of degrees parity.
11. Hamiltonian paths and cycles. Dirac theorem.
12. Graph coloring. Criterion of bipartiteness.
13. Brooks theorem.
14. Chromatic polynomial. Enumeration of acyclic orientations.
15. Edge coloring. Vizing theorem.
16. Plane and planar graphs. Euler formula.
17. Estimation of number of edges via the number of vertices; triangle free case. Non-planarity of $K_5$ and $K_{3,3}$.
18. Sylvestre problem (on configurations of points and lines.)
19. Five colors theorem.
20. Ramsey theorem.
21. Corollaries of the Ramsey theorem: Schur theorem, Erdos-Szekeres theorem.
22. Lower bounds of diagonal Ramsey numbers.
23. Large anticliques in triangle free graphs.
24. Graphs with large girth and large chromatic number.
25. Lovasz local lemma.
26. Combinatorial Nullstellensatz.
27. Cauchy-Davenport thheorem.
28. List chromatic number. List chromatic number of a bipartite planar graph does not exceed 3.
29. Matroid. Definition via independent sets. Greedy algorithm. Examples.
30. Bases, cycles, rank function of matroid.
31. Dual matroid. Rank function of the dual matroid.
32. Direct sum of matroids. Image of matroid. Matroids union.
33. Rado theorem on indepndent transversal. Generalization.
34. Rank function of the image of matroid. Rank function of matroids union. Nash-Williams theorem on a covering a graph by forests.

References

• R. L. Graham, D. E. Knuth, O. Patashnik.
Concrete mathematics: a foundation for computer science. Addison-Wesley, 1994.

• N. Alon and J. Spencer, The Probabilistic Method. John Wiley & Sons, New York, 1992.
• S. Lang. Algebra. Any edition.
• Noga Alon. Combinatorial Nullstellensatz. Comb. Probab. Comput., 8(1-2):7-29, 1999.
• J.A. Bondy and U.S.R. Murty. Graph theory with applications. University of Waterloo, 1982.
• Peter Bro Miltersen. Handbook on Randomization, volume II, chapter 19. Derandomizing Complexity Classes. Kluwer Academic Publishers, July 2001.