Course Materials for MATH20902 : Discrete Mathematics

Available Resources

Lecture Notes

The notes linked below will include everything I cover in lecture, but for additional reading I urge you to have a look at the online versions of Dieter Jungnickel's very useful book, Graphs, Networks and Algorithms. I wrote the course while studying a copy of the 2nd edition, but you might also like to look at the 4th edition, which appeared in 2013.

The table below includes links to lecture notes as well as the dates on which a given topic was covered in both the current year, 2020, and the previous one, 2019. Where possible, a date is also a hyperlink to the corresponding podcast.

You can also get the notes for the whole term in a single file.

  Dates and Podcasts
Notes 2020 2019
First Steps in Graph Theory 28 January & 31 January 28 January & 31 January
Representing Graphs & Graph Isomorphism 31 January & 4 February 31 January & 4 February
Graph Colouring 7 February 4 February & 7 February
Efficiency of Algorithms 11 February 7 February & 11 February
Walks, Trails, Paths and Connectivity 14 February & 18 February 14 February
Trees and Forests 18 February + UCU Strike 18 February, 21 February & 25 February
The Matrix-Tree Theorems 28 February + UCU Strike 25 February & 28 February
Matrix-Tree Ingredients UCU Strike 28 February & 4 March
Proof of Tutte's Matrix-Tree Theorem 6. March + UCU Strike 4 March & 7 March
Eulerian Multigraphs UCU Strike 21 March & 25 March
Hamiltonian Graphs and the Bondy-Chvátal Theorem 17 March & 20 March 28 March & 1 April
Distances in Graphs 20 March 1 April & 4 April
Tropical Arithmetic and Shortest Paths 24 March 4 April & 29 April
Critical Path Analysis 27 March 2 May
Planar Graphs 21, 24 & 28 April and 1 May 11 March, 14 March, 18 March & 21 March
Review: old exam problems 5 May 9 May

to the top

Opportunities for feedback

The main channel for formal, written feedback in this module is the coursework. It will be a problem set similar to the ones below, but devoted to an application that uses the ideas from the course. You'll prepare written solutions and I'll mark them over the Easter Break, providing both written comments and a mark. In addition, the weekly examples classes provide further opportunities for verbal feedback and—for students who bring written solutions to the exercises—on-the-spot marking and written feedback as well.

Problem Sets & Solutions

The problem sets, which appear roughly every week throughout the term, are an important part of the course. I always publish the problems and the solutions at the same time.

Problems Solutions

to the top

Coursework & Exams

Coursework Exams

to the top

Intended Learning Outcomes

Once you've successfully completed this module you should be able to:

  • Define what it means for two graphs to be isomorphic and determine, with rigorous supporting arguments, whether two (small) graphs are isomorphic.
  • Explain what the chromatic number of a graph is, determine it for small graphs and apply the idea to scheduling problems.
  • Say what it means for a graph to be Eulerian and determine whether small graphs or multigraphs are Eulerian.
  • Say what it means for a graph to be Hamiltonian and use the Bondy-Chávtal theorem to prove that a graph is Hamiltonian.
  • Construct the graph Laplacian and apply the Matrix-Tree Theorem to count the number of spanning trees or spanning arborescences contained in a graph.
  • Construct the adjacency matrix of a graph and exploit the connection between powers of the adjacency matrix to count walks. Also, define the operations of tropical arithmetic, construct the weight matrix associated with a weighted graph and use its tropical matrix powers to find the lengths of shortest paths.
  • Given a project defined by a set of tasks, along with their their durations and prerequisites, use critical path analysis to determine how quickly the project can be completed.
  • Say what it means for a graph to be planar; state and apply Kuratowski's theorem and determine whether a graph is planar or not.