Course description: A brief overview of the basic concepts of graph theory will be followed by an indepth discussion of some classical chapters of graph theory as well as some aspects of a current area: information theoretic graph theory.
Topics covered:
Topic 
Contents 
Basics 
Graphs, paths and cycles, independent sets, cliques, trees, spanning trees, cycle structure of graphs, Euler tours. 
Hamilton cycles 
Sufficient conditions for Hamiltonicity, theorems of Dirac, Ore,
Pósa, Chvátal. 
Matchings 
Hall's theorem, König theorem, Tutte's theorem, stable matchings, GaleShapley theorem. 
Colorings 
Chromatic number, its relation to the clique number, Zykov’s and Mycielski’s constructions, coloring edges, Vizing’s theorem, list coloring, chromatic number of the plane. 
Planarity 
Planar and plane graphs, Kuratowski’s theorem, Euler’s formula, 5color theorem, Thomassen’s theorem on list coloring of planar graphs, graph minors. 
Extremal graph theory 
Turán's theorem, ErdősStoneSimonovits theorem, ErdősGallai theorem, ErdősSós conjecture, extremal graphs not containing cycles of a given length, saturation, ErdősHajnalMoon theorem. 
Network flows and connectivity 
Networks, FordFulkerson theorem, vertex and edge connectivity, Menger's theorems, Mader’s theorem. 

