B8.5 Graph Theory (2025-26)
Main content blocks
- Lecturer: Profile: Oliver Riordan
The main aim of the course is to introduce the fundamental ideas of Graph Theory, and some of the basic techniques of combinatorics.
Trees and their characterization.
Euler circuits; long paths and cycles.
Vertex colourings: Brooks' theorem, chromatic polynomial.
Edge colourings: Vizing's theorem.
Planar graphs, including Euler's formula, dual graphs.
Maximum flow - minimum cut theorem: applications including Menger's theorem and Hall's theorem.
Tutte's theorem on matchings.
Extremal Problems: Turan's theorem, Zarankiewicz problem, Erdős-Stone theorem.
Section outline
-
-
2025 Lecture notes. Minor changes from 2024 version (including some notation); will be updated as the course progresses, generally in advance of the lectures. You can always look further ahead in the 2024 version but beware notation differences!
-
Self-study practice sheet, especially for those who did not do Part A Graph Theory (many of the questions are from the sheets for that course). These problems will not be covered in the classes.
-
For the first class. Covers material from weeks 1 and 2. Section A is for self-study; solutions will be provided. The core material is Section B, to be handed in for the first class. Section C is optional, but compulsory for MFoCS students; solutions will be provided.
-
-
Registration start: Monday, 6 October 2025, 12:00 PMRegistration end: Friday, 7 November 2025, 12:00 PM
-
Class Tutor's Comments Assignment
Class tutors will use this activity to provide overall feedback to students at the end of the course.
-