Please read our student and staff community guidance on COVID-19
Skip to main content Skip to navigation

MA4J3 Graph Theory

Lecturer: Vadim Lozin

Term(s): Term 1

Status for Mathematics students: List C

Commitment: 30 lectures

Assessment: 3 hour examination (100%)

Prerequisites: Familiarity with MA241 Combinatorics and MA252 Combinatorial Optimisation will be useful

Leads To:


Graph theory is a rapidly developing branch of mathematics that finds applications in other areas of mathematics as well as in other fields such as computer science, bioinformatics, statistical physics, chemistry, sociology, etc. In this module we will focus on results from structural graph theory. The module should provide an overview of main techniques with their potential applications. It will include a brief introduction to the basic concepts of graph theory and it will then be structured around the following topics:

Structural graph theory:

  • Graph decompositions
  • Graph parameters

Extremal graph theory:

  • Ramsey’s Theorem with variations
  • Properties of almost all graphs

Partial orders on graphs:

  • Minor-closed, monotone and hereditary properties
  • Well-quasi-ordering and infinte antichains


To introduce students to advanced methods from structural graph theory.


By the end of the module the student should be able to:

  • State basic results covered by the module
  • Understand covered concepts from graph theory
  • Use presented graph theory methods in other areas of mathematics
  • Apply basic graph decomposition techniques


Bollobás, Béla (2004), Extremal Graph Theory, New York: Dover Publications, ISBN 978-0-486-43596-1
Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4

Additional Resources

Archived Pages: 2012 2014 2015 2016 2018

Year 1 regs and modules
G100 G103 GL11 G1NC

Year 2 regs and modules
G100 G103 GL11 G1NC

Year 3 regs and modules
G100 G103

Year 4 regs and modules

Archived Material
Past Exams
Core module averages