Graphs are fundamental structures in mathematics and computer science, appearing in everything from network design to combinatorial optimization. While you may have previously explored the algorithmic aspects of graph theory, this course focuses on its structural foundations. We will delve into fundamental theorems and rigorous proofs that explain why graphs behave the way they do.
We will start with the basics—trees, cycles, paths, and Eulerian graphs—before progressing to more advanced topics such as Hamiltonian graphs, matchings, connectivity, planar graphs, and graph coloring. Toward the end, we will introduce the theory of graph minors, a powerful framework in structural graph theory. Along the way, we will encounter key results like Menger's theorem on connectivity, Kuratowski's theorem on planarity, and Vizing's theorem on edge coloring. These theorems not only highlight the rich structure of graphs but also provide insights that extend to areas such as combinatorics and optimization.
To complement the theoretical discussions, we will have regular exercise sessions every few lectures, where students will engage with structural problems and explore their algorithmic implications. These sessions will bridge the gap between theory and computation through hands-on problem-solving.
The goal of this course is to ensure that, by the end of the semester, students develop a stronger foundation in the core concepts of graph theory and gain a deeper appreciation for the structures that underpin graph algorithms.
You can register at the course in the moodle page !
