Graph Theory

Fall 2026

Announcements

• [6/11]: To help you prepare for the midterm exam, you can find the subject from 2025 and 2024 here and here. Recall, however, that as we mentioned in class, this year's midterm will only cover material up to and including Menger's theorem (that is, coloring is not going to be covered in the exam this year).
• [6/11]: Exceptionally, the two TD groups will have a common session on Monday 9/11. We will meet in room F303 at 10:15.
• [3/11]: Due to the university closure this week, the class session scheduled for Wednesday 4/11 at 15:30 will be held online via Teams. The connection information is the following: link, Meeting ID: 344 084 136 067 016 9, Passcode: fC7x6VQ6
• [22/10]: The midterm exam has been scheduled for Monday 16/11 at 10:15-11:45 in Amphitheater 8.
• [14/10]: Due to the continuing closure, the CM session scheduled for today 14/10 at 15:30 is also canceled.
• [13/10]: Due to the continuing closure, the CM session scheduled for today 13/10 at 12:00 is also canceled.
• [12/10]: Due to the university closure today and following the decision voted by the MIDO department last week, the TD sessions scheduled for today 12/10 are canceled. We will update this page with further information throughout the week.
• [6/10]: Due to the university closure the class session scheduled for Wednesday 7/10 at 15:30 will be held online via Teams. The connection information is the following: link, Meeting ID: 367 363 116 091 926, Passcode: dH3G9f2R
• [29/9]: There have been two updates to our schedule below: the session of Wednesday 21/10 has been moved to Tuesday 13/10 (to avoid the school holiday period) and the session missing due to the holiday of Wednesday 11/11 will take place on Tuesday 10/11. The date of the midterm exam has not been fixed yet, watch here for updates.
• [9/9]: First class. Welcome!

General Information

The topic of this course is Graph Theory. Graphs are mathematical objects that can model complex networks with varying applications. In this course we take an approach that focuses on the mathematical side of things: we want to understand and formally prove interesting properties exhibited by graphs. We will do this from a computer scientist's perspective, often pausing to ponder the algorithmic and complexity-theoretic properties of the objects we study.

More information on the topics to be covered appears in the schedule below (which will be updated during the semester).

The course consists of 1.5 hours of weekly lectures, followed by 1.5 hours of TD (exercise sessions).

Grading: Your final grade is the result of the formula 0.7E+0.3CC, where E is your grade in the final exam and CC is your grade in a midterm exam that will be organized at some point in the middle of the semester.

Additional Material / Bibliography

• Introduction to Graph Theory by D. West.
• Graph Theory by R. Diestell.

Course Schedule

Here you will find a tentative schedule (updated regularly throughout the semester) and the slides we will use in class.

TD