## Topics covered

#### The Basics

• Lecture 1: Basic definitions
• Lecture 2: Sperner's Lemma and Brouwer's Fixed Point Theorem.
• Lecture 3: Paths, Cycles, Girth, Diameter and their relation to vertex degrees. The Moore bound.
• Lecture 4: Edge and vertex connectivity. Cut vertices, bridges and Trees.
• Lecture 5: Bipartite graphs and odd cycles. Whitney's Theorem. Euler paths and cycle.

#### Cayley's Formula and Matrix Tree Theorem

• Lecture 6: Cayley formula using recursion and using bijections (Prufer Codes).
• Lecture 7: Cayley formula by direct counting. Matrix-tree Theorem using Binet-Cauchy Theorem.
• Lecture 8: The Matrix-Tree Theorem for directed rooted spanning trees (Tutte).

#### Matching and Covering

• Lecture 9: Theorems of Hall and Berge.
• Lecture 10: Hall's Theorem using augmenting paths. Applications of Hall's Theorem: defect Hall Theorem, Marriage Theorem, and the Theorems of Petersen and Konig-Egervary.
• Lecture 11: Dilworth's Theorem via Konig-Egervary Theorem. Mirsky's Theorem (dual Dilworth Theorem).
• Lecture 12: Birkhoff/von-Neumann Theorem. Sperner's Theorem. Stable Matchings (Gale-Shapley Theorem).
• Lecture 13: Theorems of Tutte, Petersen and Gallai-Milgram.
• Lecture 14: Tutte-Berge Formula. Tutte's matrix condition for existence of perfect matching.

#### Connectivity

• Lecture 15: k-connected subgraphs in dense graphs (Mader's Theorem). Menger's Theorem.
• Lecture 16: Variant's of Menger's Theorem (edges, vertices and global). Structure of 2-connected graphs; Block and Ear Decompositions.
• Lecture 17: Circulations, Flows and the Max-Flow-Min-Cut Theorem. Relation to Menger's Theorem.

#### Hamilton Cycles

• Lecture 18: Hamilton Cycles and the Theorems of Dirac and Chvatal-Erdos.
• Lecture 19: Hamiltonian degree sequences (Chvatal's Theorem). Ore's Theorem. De-Bruijn sequences.

#### Coloring

• Lecture 20: Vertex and edge colorings and their relation to max-degree
• Lecture 21: Chromatic number and degeneracy. Edge-coloring bipartite graphs (Konig's Theorem).
• Lecture 22: Vizing's Theorem. Basic properties of k-critical graphs.
• Lecture 23: Structure of non 3-connected k-critical graphs. Brook's Theorem.
• Lecture 24: Triangle-free graphs of high chromatic number. The Conjectures of Hajos and Hadwiger. Proof for k=4.

#### Extremal Problems

• Lecture 25: Theorems of Ramsey, Schur and Turan.
• Lecture 26: Graph Ramsey Numbers of Clique/Tree and Induced Star/Path/Clique. Topological Minors in sparse graphs .
• Lecture 27: Highly connected graphs are highly linked. High-degree minors in sparse graphs of high girth.

#### Planar Graphs

• Lecture 28: Planar graph, Dual graph, Euler formula. Comments on Kuratowski's Theorem and the 4-Color Theorem.
• Lecture 29: The 5-Color Theorem and Tait's "proof" of the 4-Color Theorem.