Lecture 1 - Introduction: Vertex cover and independent set Lecture 2 - Matchings: Konig’s theorem and Hall’s theorem Lecture 3 - More on Hall’s theorem and some applications Lecture 4 - Tutte’s theorem on existence of a perfect matching Lecture 5 - More on Tutte’s theorem Lecture 6 - More on Matchings Lecture 7 - Dominating set, path cover Lecture 8 - Gallai – Millgram theorem, Dilworth’s theorem Lecture 9 - Connectivity: 2-connected and 3-connected graphs Lecture 10 - Menger’s theorem Lecture 11 - More on connectivity: k- linkedness Lecture 12 - Minors, topological minors and more on k- linkedness Lecture 13 - Vertex coloring: Brooks theorem Lecture 14 - More on vertex coloring Lecture 15 - Edge coloring: Vizing’s theorem Lecture 16 - Proof of Vizing’s theorem, Introduction to planarity Lecture 17 - 5- coloring planar graphs, Kuratowsky’s theorem Lecture 18 - Proof of Kuratowsky’s theorem, List coloring Lecture 19 - List chromatic index Lecture 20 - Adjacency polynomial of a graph and combinatorial Nullstellensatz Lecture 21 - Chromatic polynomial, k - critical graphs Lecture 22 - Gallai-Roy theorem, Acyclic coloring, Hadwiger’s conjecture Lecture 23 - Perfect graphs: Examples Lecture 24 - Interval graphs, chordal graphs Lecture 25 - Proof of weak perfect graph theorem (WPGT) Lecture 26 - Second proof of WPGT, Some non-perfect graph classes Lecture 27 - More special classes of graphs Lecture 28 - Boxicity,Sphericity, Hamiltonian circuits Lecture 29 - More on Hamiltonicity: Chvatal’s theorem Lecture 30 - Chvatal’s theorem, toughness, Hamiltonicity and 4-color conjecture Lecture 31 - Network flows: Max flow mincut theorem Lecture 32 - More on network flows: Circulations Lecture 33 - Circulations and tensions Lecture 34 - More on circulations and tensions, flow number and Tutte’s flow conjectures Lecture 35 - Random graphs and probabilistic method: Preliminaries Lecture 36 - Probabilistic method: Markov’s inequality, Ramsey number Lecture 37 - Probabilistic method: Graphs of high girth and high chromatic number Lecture 38 - Probabilistic method: Second moment method, Lovasz local lemma Lecture 39 - Graph minors and Hadwiger’s conjecture Lecture 40 - More on graph minors, tree decompositions

Lecture 1 - Introduction: Vertex cover and independent set Lecture 2 - Matchings: Konig’s theorem and Hall’s theorem Lecture 3 - More on Hall’s theorem and some applications Lecture 4 - Tutte’s theorem on existence of a perfect matching Lecture 5 - More on Tutte’s theorem Lecture 6 - More on Matchings Lecture 7 - Dominating set, path cover Lecture 8 - Gallai – Millgram theorem, Dilworth’s theorem Lecture 9 - Connectivity: 2-connected and 3-connected graphs Lecture 10 - Menger’s theorem Lecture 11 - More on connectivity: k- linkedness Lecture 12 - Minors, topological minors and more on k- linkedness Lecture 13 - Vertex coloring: Brooks theorem Lecture 14 - More on vertex coloring Lecture 15 - Edge coloring: Vizing’s theorem Lecture 16 - Proof of Vizing’s theorem, Introduction to planarity Lecture 17 - 5- coloring planar graphs, Kuratowsky’s theorem Lecture 18 - Proof of Kuratowsky’s theorem, List coloring Lecture 19 - List chromatic index Lecture 20 - Adjacency polynomial of a graph and combinatorial Nullstellensatz Lecture 21 - Chromatic polynomial, k - critical graphs Lecture 22 - Gallai-Roy theorem, Acyclic coloring, Hadwiger’s conjecture Lecture 23 - Perfect graphs: Examples Lecture 24 - Interval graphs, chordal graphs Lecture 25 - Proof of weak perfect graph theorem (WPGT) Lecture 26 - Second proof of WPGT, Some non-perfect graph classes Lecture 27 - More special classes of graphs Lecture 28 - Boxicity,Sphericity, Hamiltonian circuits Lecture 29 - More on Hamiltonicity: Chvatal’s theorem Lecture 30 - Chvatal’s theorem, toughness, Hamiltonicity and 4-color conjecture Lecture 31 - Network flows: Max flow mincut theorem Lecture 32 - More on network flows: Circulations Lecture 33 - Circulations and tensions Lecture 34 - More on circulations and tensions, flow number and Tutte’s flow conjectures Lecture 35 - Random graphs and probabilistic method: Preliminaries Lecture 36 - Probabilistic method: Markov’s inequality, Ramsey number Lecture 37 - Probabilistic method: Graphs of high girth and high chromatic number Lecture 38 - Probabilistic method: Second moment method, Lovasz local lemma Lecture 39 - Graph minors and Hadwiger’s conjecture Lecture 40 - More on graph minors, tree decompositions