Graph Theory

Fall 2024

Announcements

• [17/12]: The final exam for our course is scheduled for Wednesday 8/1/2025, 14:00-16:00 in Amphitheater 4. The exam will cover all the material we have seen in class, but will heavily focus on the material of the second half (which was not covered in the midterm exam). The exam will be closed-book (you are not allowed to bring notes). You will not be asked to memorize and reproduce any proofs given in class, but you will be expected to know all the definition we discussed and the statements of all the theorems mentioned in the slides.
• [25/11]: Solutions for the midterm exam can be found here.
• [2/11]: A make-up course session has been scheduled for this Thursday 7/11, 15:30-17:00 (currently in room A309). This session is meant to replace the session of 1/11, which was a public holiday.
• [25/10]: Midterm Exam: The material to study for the exam of 8/11 is the following: All lectures up to and including Menger's theorem, Cuts and Connectivity (but not the Graph Coloring lecture) and TD 1-5.
• [4/10]: Midterm Exam: The midterm exam has been scheduled for Friday 8/11 during our regular class time (8:30-10:00).
• [23/9]: A make-up course session has been scheduled for this Friday 27/9. As a result the schedule is updated as follows: we will have 3 hours of course on Friday 27/9, 8:30-11:45 (currently scheduled in P301 and P309, but check your online schedule for update). The TD session that was planned for Friday morning is instead moved to Friday afternoon, on the same day (27/9), 15:30-17:00 (currently in room A411).
• [17/9]: The TD session of Thursday 19/9 is postponed. The reason is that we have to have at least one course session before discussing exercises. We will post further information about when this session will be made in the coming days. Therefore, both groups will attend class for the first time on Friday 20/9 at 8:30 (if all goes well!).
• [13/9]: Dauphine University is closed today!. As a result there will be no class today. We will post information about how today's session will be made up later. In the meantime, feel free to look at the slides.
• [13/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, most likely on 25/10 on 8/11.

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