\textbf{Instructor:} Kristóf Bérczi\footnote{Department of Mathematics, E\"{o}tv\"{o}s Lor\'{a}nd University, Budapest, Hungary}

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.

\subsection*{Topics}

\begin{enumerate}[1.]
    \item \textbf{Basics:} Graphs, degrees, paths and cycles, independent sets, cliques, isomorphism, subgraphs, complement of a graph, trees, breadth-first search, depth-first search, applications.
    
    \item \textbf{Trees:} Pr\"{u}fer code, Cayley's theorem, exchange properties of spanning trees, Kruskal's algorithm, Matrix-Tree Theorem.
    
    \item \textbf{Eulerian Tours and Hamilton Cycles:} K\"{o}nigsberg bridges problem, Euler's theorem, Hamiltonian cycles and paths, necessary conditions, sufficient conditions (Dirac, Ore, P\'{o}sa, Chv\'{a}tal).
    
    \item \textbf{Shortest Paths:} PERT method, Dijkstra's algorithm, Gallai's theorem.
    
    \item \textbf{Matchings in Bipartite Graphs:} K\H{o}nig-Hall-Frobenius theorem, with K\H{o}nig's algorithm, Egerv\'{a}ry's theorem and algorithm, stable matchings, Gale-Shapley algorithm.
    
    \item \textbf{Matchings in General Graphs:} Tutte's theorem, matchability of a subset, Petersen's theorem.
    
    \item \textbf{Colorings:} Chromatic number and clique number, Mycielski's construction, Brooks' theorem, edge-chromatic number, Vizing's theorem, list colorings.
    
    \item \textbf{Flows and Circulations:} Hoffman's theorem, Max Flow-Min Cut Theorem, Menger's theorems, disjoint paths between terminal pairs, nowhere-zero flows, balanced orientations.
    
    \item \textbf{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.
    
    \item \textbf{Higher Connectivity:} Highly edge- and node-connected graphs, block decompositions, ear decompositions.
    
    \item \textbf{Orientations:} Degree bounds, Hakimi's lemma, Luigi's conjecture, F-avoiding orientations.
    
    \item \textbf{Partially Ordered Sets:} Dilworth's theorem.
    
    \item \textbf{Perfect Graphs:} Basic examples, perfectness of comparability graphs, Perfect Graph Theorem, Strong Perfect Graph Theorem.
\end{enumerate}
