# Graph Theory - 0366.3267

## Noga Alon and Wojciech Samotij (nogaa@tau.ac.il, samotij@tau.ac.il ) Fall 2015-2016, Sunday 15-18, Shenkar 105 School of Mathematical Sciences, Tel-Aviv University

### Procedural Matters:

Prerequisite Courses: Discrete Mathematics or Introduction to Combinatorics and Graph Theory, Linear Algebra, Introduction to Probability.
Exercises will be given during the course and will account for 10% of the final grade. There will also be a final exam.

### Text books:

Most of the topics covered in the course appear in the books listed below (especially the first three).

Graph Theory,

by J. A. Bondy and U. S. R. Murty, Springer, 2008.

Introduction to Graph Theory,

by D. B. West, Prentice Hall, 1996.

Graph Theory,

by R. Diestel, Springer, 1997.

The Probabilistic Method, third edition,

by N. Alon and J. H. Spencer, Wiley, 2008.

### Brief syllabus:

Graphs and subgraphs, trees, connectivity, Euler tours, Hamilton cycles, matchings, Hall's Theorem and Tutte's Theorem, edge coloring and Vizing's Theorem, independent sets, Turan's Theorem and Ramsey's Theorem, vertex coloring, planar graphs, directed graphs, probabilistic methods and linear algebra tools in Graph Theory.
More relevant information, to be updated during the term, appears in: Graph Theory

Additional relevant information, including exams from previous years, appears in: Graph Theory

### Course Outline:

1. Oct. 18
Basic definitions and properties: graph isomorphism, the adjacency and the incidence matrices, subgraphs and induced subgraphs, the complement and the line graph of a graph, complete and empty graphs, cliques and independent sets, bipartite graphs, vertex degrees, walks, trails, paths and cycles, girth and circumference, connectivity and connected components, Sperner's lemma (in dimension 2).
2. Oct. 25
Brouwer's fixed point theorem (in dimension 2), trees and forests, basic properties of trees, edge contraction and the contraction-deletion recursive formula for the number of spanning trees, Cayley's formula, Kirchhoff's matrix tree theorem.
3. Nov. 1
Proof(s) of Kirchhoff's matrix tree theorem, connectivity of a graph.
4. Nov. 8
Highly connected subgraphs in graphs of large average degree (Mader's theorem), edge-connectivity, structural characterization of 2-connected graphs ("ear decomposition"), blocks and block-decompositions, Menger's theorem.
5. Nov. 15
Proof of Menger's theorem, Eulerian circuits, Hamilton cycles, Dirac's theorem, Ore's theorem.
6. Nov. 22
The Chvatal-Erdos theorem, matchings, factors, and vertex covers, Hall's marriage theorem and corollaries: every nonempty regular bipartite graph has a perfect matching, every regular graph with positive even degree has a 2-factor, systems of distinct representatives, Konig's theorem, Tutte's matching theorem.
7. Nov. 29
Every bridgeless 3-regular graph has a perfect matchingr, vertex coloring, the Nordhaus Gaddum theorem, the greedy coloring algorithm, degeneracy of a graph, Brooks' theorem.
8. Dec. 6
Color-critical graphs, color-critical graphs have no cutvertices, every (k+1)-critical graph is k-edge-connected (Dirac's theorem), a construction of triangle-free graphs with large chromatic number, graphs with large chromatic number and no short cycles, edge coloring, Konig's theorem.
9. Dec. 13
Hanukkah
10. Dec. 20
Edge coloring: Vizing's Theorem. Ramsey's Theorem, the Ramsey numbers r(k,ell), their computation for small k, ell, and the upper bound of Erdos and Szekeres.
11. Dec. 27
Erdos' probabilistic lower bound for the Ramsey number r(k,k), Multicolor Ramsey numbers, Schur's Theorem. Extremal Graph Theory: Turan's Theorem.
12. Jan. 3
The theorem of Kovari, Sos and Turan. Planar graphs: Kuratowski's Theorem, Euler's Formula, comments on the Four Color Theorem and a proof that five colors suffice.
13. Jan. 10
Tools from linear algebra: the Graham Pollak Theorem (with the proof of Tverberg), Fisher's Inequality, 3 regular subgraphs.
14. Jan. 17
Solution of homework assignments.

## Exercises

### List of Theorems

Remark: The final grade was determined as follows: A=average grade of 4 homework assignments. B=grade of final exam, where the weight of the best 4 answers is 0.9 and that of the fifth answer is 0.1. C=max(B,0.9B+0.1A). The final grade is F=C, unless C is bigger than 50 and smaller than 60, in this case F=60.

redesigned by barak soreq