Graph Theory

Graph Theory

MSc Lecture - Summer 2025

Links

Courses IT-Systems Engineering , Algorithm Engineering Moodle

Description

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 !

Requirements

This course is designed for master students who enjoy mathematical reasoning and want to develop a deeper understanding of graph structures. The lectures will be held in English!

Learning and teaching methods

In the lecture we will work problem-oriented and partly interactive. To achieve this, lecture and exercise sessions will be mixed as needed.

Grading

The participation in the regular exercise sessions is recommended for active learning. Toward the end of the semester, each student will select a topic from a provided list and deliver a one-hour lecture (using the board), followed by a Q&A session on the topic, which contributes 70% to the final grade. The remaining 30% will be based on a written report about the chosen topic.
 

Lecture Team

The following persons are involved in this lecture: