Course description: The course begins with an overview of the fundamental concepts of graph theory, followed by an in-depth discussion of some classical topics as well as some aspects of a current area: information theoretic graph theory.

Topics covered: (tentative)

1. Basics: Graphs, degrees, paths and cycles, independent sets, cliques, isomorphism, subgraphs, complement of a graph, trees, breadth-first search, depth-first search, applications.
2. Trees: Prüfer code, Cayley’s theorem, exchange properties of spanning trees, Kruskal’s algorithm, Matrix-tree Theorem.
3. Orientations and Eulerian tours: Königsberg bridges problem, Euler’s theorem
4. Hamilton cycles: Hamiltonian cycles and paths, necessary conditions, sufficient conditions (Dirac, Ore, Pósa, Chvátal)
5. Shortest paths: PERT method, Dijsktra’s algorithm, Gallai’s theorem
6. Matchings: Kőnig-Hall-Frobenius theorem, Kőnig’s algorithm, stable matchings, Gale-Shapley algorithm, Tutte’s theorem, matchability of a subset
7. Colorings: Chromatic number and clique number, Mycielski’s construction, Brooks’ theorem, edge-chromatic number, Vizing’ theorem, list colorings, chromatic polynomial, unit distance graph.
8. Flows: Max Flow-Min Cut Theorem, Menger’s theorems, disjoint paths between terminal pairs, nowhere-zero flows, balanced orientations
9. Planar graphs: Four Color Theorem, Euler’s formula, bounding the number of edges of planar graphs, Kuratowski’s theorem, graph minors, Wagner’s theorem, Five Color Theorem.
10. Higher connectivity: Highly edge- and node-connected graphs, block decompositions, ear decompositions.
11. Partially ordered sets: Dilworth’s theorems.
12. Perfect graphs: Basic examples, perfectness of comparability graphs, the Perfect Graph Theorem, the Strong Perfect Graph Theorem.