Course: B8.5 Graph Theory (2025-26) | Mathematical Institute

Home Calendar Help

Lecturer: Profile: Oliver Riordan

Course information

General prerequisites:

Part A Graph Theory is recommended.

Course term: Michaelmas

Course lecture information: 16 lectures

Course weight: 1

Course level: H

Assessment type: Written Examination

Course overview:

Graphs (abstract networks) are among the simplest mathematical structures, but nevertheless have a very rich and well-developed structural theory. Since graphs arise naturally in many contexts within and outside mathematics, Graph Theory is an important area of mathematics, and also has many applications in other fields such as computer science.

The main aim of the course is to introduce the fundamental ideas of Graph Theory, and some of the basic techniques of combinatorics.

Learning outcomes:

The student will have developed a basic understanding of the properties of graphs, and an appreciation of the combinatorial methods used to analyze discrete structures.

Course synopsis:

Introduction: basic definitions and examples.

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

Select section General

Collapse Expand
General

Collapse all Expand all
- Select activity Announcements
  
  Announcements Forum
- Select activity Reading List
  
  Reading List URL
- Select activity Discussion Forum
  
  Discussion Forum
Select section Course Materials

Collapse Expand
Course Materials
- Select activity Notation summary
  
  Notation summary File
- Select activity Lecture Notes (now complete)
  
  Lecture Notes (now complete) File
  
  2025 Lecture notes. Minor changes from 2024 version, including some notation.
  
  NB in the planar graphs section, some material (shown in blue) is non-examinable this year.
  
  [P_4 corrected to P_3 in Figure 2]
- Select activity Problem Sheet 0
  
  Problem Sheet 0 File
  
  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.
- Select activity Problem Sheet 0 Solutions
  
  Problem Sheet 0 Solutions File
- Select activity 2024 Lecture Notes
  
  2024 Lecture Notes File
- Select activity Problem Sheet 1
  
  Problem Sheet 1 Assignment
  
  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.
  
  File with solutions to Sections A and C now available. Do try the questions first!
- Select activity Problem Sheet 2
  
  Problem Sheet 2 Assignment
  
  For the second class. Covers material from weeks 3 and 4. First look at the file without solutions.
  
  Section A is for self-study; solutions are in the second file, but try the questions before looking at them. The core material is Section B, to be handed in for the second class. Section C is optional, but compulsory for MFoCS students; solutions are in the second file.
- Select activity Problem Sheet 3
  
  Problem Sheet 3 Assignment
  
  For the third class. Covers material from weeks 5 and 6. First look at the file without solutions.
  
  Section A is for self-study; solutions are in the file GT_problems3_solnsA, but try the questions before looking at them. The core material is Section B, to be handed in for the second class.
  
  Section C is optional, but compulsory for MFoCS students. Some of these questions are more exploratory, so it's recommended to think about them without looking at solutions and see what you can do. Solutions have been now, though.
- Select activity Problem Sheet 4
  
  Problem Sheet 4 Assignment
  
  For the final class. Covers material from weeks 7 and 8. First look at the file without solutions.
  
  Section A is for self-study; solutions are in the file GT_problems4_solnsA+C, but try the questions before looking at them. The core material is Section B, to be handed in for the final class.
  
  Section C is optional, but compulsory for MFoCS students. It's again highly recommended to think about these properly before looking at the solutions, which are available.
Select section Intercollegiate Classes

Collapse Expand
Intercollegiate Classes
- Select activity Class Signup
  
  Class Signup Class registration
  
  Registration start: Monday, 6 October 2025, 12:00 PM
  
  Registration end: Friday, 7 November 2025, 12:00 PM
- Select activity Class Tutor's Comments
  
  Class Tutor's Comments Assignment
  
  Class tutors will use this activity to provide overall feedback to students at the end of the course.
  
  Not available unless: You have signed up to a class

Main content blocks

Section outline

General

Course Materials

Intercollegiate Classes