Course description: The course begins with an overview of the fundamental concepts of graph theory, followed by a detailed discussion of classical topics in both structural and algorithmic graph theory.

Topics covered (tentative):

• Basics: Graphs, degrees, paths and cycles, independent sets, cliques, isomorphism, subgraphs, complement of a graph, trees, breadth-first search, depth-first search, applications.
• Trees: Prüfer code, Cayley's theorem, exchange properties of spanning trees, Kruskal's algorithm, Matrix-tree Theorem.
• Eulerian tours and Hamilton cycles: Königsberg bridges problem, Euler's theorem, Hamiltonian cycles and paths, necessary conditions, sufficient conditions (Dirac, Ore, Pósa, Chvátal).
• Shortest paths: PERT method, Dijsktra's algorithm, Gallai's theorem.
• Matchings in bipartite graphs: Kőnig-Hall-Frobenius theorem, Kőnig's algorithm, Egerváry's theorem and algorithm, stable matchings, Gale-Shapley algorithm.
• Matchings in general graphs: Tutte's theorem, matchability of a subset, Petersen's theorem.
• Colorings: Chromatic number and clique number, Mycielski's construction, Brooks' theorem, edge-chromatic number, Vizing' theorem, list colorings.
• Flows and circulations: Hoffman's theorem, Max Flow-Min Cut Theorem, Menger's theorems, disjoint paths between terminal pairs, nowhere-zero flows, balanced orientations.
• 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, Schnyder labelings, drawing planar graphs on grids.
• Higher connectivity: Highly edge- and node-connected graphs, block decompositions, ear decompositions.
• Orientations: Degree bounds, Hakimi's lemma, Luigi's conjecture, F-avoiding orientations.
• Partially ordered sets: Dilworth's theorems.
• Perfect graphs: Basic examples, perfectness of comparability graphs, the Perfect Graph Theorem, the Strong Perfect Graph Theorem.