In Term 1, 2022 I am teaching half of MATH1081 Discrete Mathematics. I'm teaching the topics on sets and functions, number theory, and graph theory.

In Term 3, 2022 I will teach the Algebra half of MATH2701 Abstract Algebra and Fundamental Analysis.

MATH5425 Graph Theory

MATH5425 Graph Theory is a 6 UOC level V course which covers several topics in classical graph theory, as well as results proved using the probabilistic method. This course has run roughly every 2 years since 2006, and was last offered in Term 1, 2021. Hopefully it will be offered again in 2023.

Graphs are fundamental objects in combinatorics, which can be used to model the relationships between the members of a network or system. They have many applications in areas such as computer science, statistical physics and computational biology. Specifically, a graph is a set of vertices and a set of edges, where (generally) an edge is an unordered pair of distinct vertices. The course covers various combinatorial aspects of graph theory and introduces some of the tools used to tackle graph theoretical questions. A particular focus will be on the use of probability to answer questions in graph theory. This is known as the "Probabilistic Method", initiated by Erdős.

Topics include:

  • matchings, coverings and packings,
  • connectivity,
  • graph colourings: vertex colourings and edge colourings,
  • planar graphs,
  • Ramsey theory,
  • the probabilistic method,
  • random graphs.

There are no formal prerequisites for this course, though students should be familiar with set theory, logic and proofs. There is a strong emphasis on proof in the course, and students are asked to construct their own proofs in the assessment tasks.

The main textbook is R. Diestel, Graph Theory 5th edn. (Springer, 2017), which is also available online at diestel-graph-theory.com.

Some material is also drawn from

  • B. Bollobás, Modern Graph Theory (Cambridge University Press, 1998),
  • N. Alon and J. Spencer, The Probabilistic Method (Wiley 2000).


Here is a list of past Honours students, as well as some possible topics for an Honours project.